Description

There are $N$ idols standing in a line, coming from $M$ different bands. Each band has at least one idol.

We want to rearrange the line so that idols from the same band stand together contiguously. The way to rearrange is: let some idols leave the line (the remaining idols do not move), then let the removed idols return one by one to fill the vacated positions; they may return to any empty positions.

What is the minimum number of idols that must leave the line?

Input Format

The first line contains $2$ integers $N$ and $M$.

Then there are $N$ lines, each containing an integer $a_i(1\le a_i \le M)$, representing the band ID of the $i$-th idol in the line.

Output Format

Output a single integer, the answer.

12 4
1
3
2
4
2
1
2
3
1
1
3
4

7

Hint

Sample explanation:

1  3   √
3  3
2  3   √
4  4
2  4   √
1  2   √
2  2
3  2   √
1  1
1  1
3  1   √
4  1   √

Constraints:

• For $20\%$ of the testdata, $N\le 20, M=2$.
• For $40\%$ of the testdata, $N\le 100, M\le 4$.
• For $70\%$ of the testdata, $N\le 2000, M\le 10$.
• For all testdata, $1\le N\le 10^5, M\le 20$.

Translated by ChatGPT 5