Get Min Amount (Contiguous Quality)

One operation chooses x and y and changes every x in the array to y, at a cost equal to the current number of occurrences of x. The goal is for the occurrences of each remaining value to form one contiguous segment; find the minimum total cost.

输入格式

The first line contains n (1..200000), and the second line contains n quality values (−10⁹..10⁹).

输出格式

Output a single integer answer.

样例 1

输入：

7
7 7 5 7 3 5 3

输出：

4

样例 2

输入：

4
1 1 2 2

输出：

0

样例 3

输入：

3
1 2 1

输出：

1

样例说明

Example 1: three values interleave within the same closed block; keep the 7 that appears 3 times and change the other 4 positions to 7, cost 4. Example 2: every class is already contiguous, cost 0. Example 3: change the middle 2 to 1, cost 1.