405093: GYM101790 C Keys assignment

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Keys assignmenttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

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

Output

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

ExamplesInput
5 2
1 3 1 2 3
Output
3
Input
5 1
1 1 2 2 2
Output
2
Input
8 3
1 2 3 1 2 3 1 3
Output
3
Note

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.

加入题单

上一题 下一题 算法标签: