Reordering Idols

You are given a lineup of N idols coming from M different bands. It is guaranteed that each band appears at least once. Your task is to rearrange the lineup so that all idols from the same band stand consecutively.

The only allowed operation is as follows: choose some idols to remove from the lineup (the remaining idols keep their positions), and then, reinsert the removed idols back into the vacant positions in an arbitrary order. Note that the relative order of the idols that are not removed remains unchanged.

In the final arrangement, for every band, all idols belonging to that band must appear in one contiguous block.

Observation: Let \( f(i) \) be the maximum length of a contiguous block in the original lineup that consists solely of idols from band \( i \). Then an optimal strategy is to avoid moving idols in such a longest contiguous block for each band \( i \). Hence, the answer is given by

[ \text{answer} = N - \sum_{i=1}^{M} f(i) ]

Compute the minimum number of idols that must be removed.

inputFormat

The first line contains two integers N and M (1 ≤ M ≤ N), representing the number of idols and the number of bands respectively.

The second line contains N integers, where the j-th integer (1-indexed) indicates the band id of the idol at position j. Each band id is an integer between 1 and M and every band appears at least once.

outputFormat

Output a single integer: the minimum number of idols that need to be removed so that after reordering the removed idols appropriately, all idols from the same band stand consecutively in the final lineup.

sample

3 2
1 2 1

1