Food Display Arrangement

Interview

Time limit1sMemory limit1024 MB

Summary

Given a row of food type IDs, find the fewest types to move to the ends so that every remaining type forms one contiguous block.

Level: Medium5 of 10
Topics: Greedy, Sorting, Hash map
Solved: No attempts yet

Problem

Your friend Thomas is working on food display arrangements (FDA). All the food is lined up in a long row (table). An FDA is aesthetically pleasing if all food of the same type is next to each other. Thomas can reorganize the FDA by picking up all the food of one type and placing it at either end of the table, at the beginning or at the end. The display can be extended at the ends to hold any amount of moved food. Find the minimum number of reorganization steps needed to make the FDA aesthetically pleasing. You only need to report the number of steps, not the steps themselves.

Input

The first line contains an integer $n$ ( $1 \le n \le 100000$ ), the number of food items. The second line contains $n$ space-separated integers $a_i$ ( $1 \le a_i \le 1000000000$ ), the type ID of the $i$ -th food item.

Output

Print the minimum number of reorganization steps needed to group all food of each type together by moving whole types to the beginning or the end.

Hint

In the first sample, moving all food of type 2 to one end and all food of type 7 to one end takes 2 moves.

Examples2

Example 1
Input
```
15
8 8 2 8 7 8 1 1 3 7 3 4 2 4 7
```
Expected output
```
2
```
Example 2
Input
```
10
1 2 3 4 5 1 2 3 4 5
```
Expected output
```
4
```