405093: GYM101790 C Keys assignment

You are playing a computer game, where you must successively cast N spells (some of them may be repeated).

There are K keys on the keyboard that can be used to assign spells.

During the game, you may assign different spells to the same key. But at the moment of pressing the key, the last assigned to this key spell will be casted.

Determine the minimum number of spell assignments that will be necessary to complete the game. Initially no spells are assigned to any key.

The first line contains two integers N (1 ≤ N ≤ 10⁵) and K (1 ≤ K ≤ 10⁵), denoting the number of spells and the number of keys correspondingly.

The second line contains N numbers A_i (1 ≤ A_i ≤ N), denoting the spell numbers in the order in which they must be casted to complete the game.

Display the minimum total number of spell assignments to a key.

5 2
1 3 1 2 3

3

5 1
1 1 2 2 2

2

8 3
1 2 3 1 2 3 1 3

3

Let's consider the first example. First, the player can assign the spell 1 to the first key and press it. Then he can assign the spell 3 to the second key and press it. Then, without performing any new assignments, he simply presses the first key. Then it is advantageous for him to assign the spell 2 to the first key and press it, and in the end he just presses the second key.