Problem : 28 - 看動畫

Problem Statistics

Solved Member: 26　　Submission: 169　　User Tried: 32

Statement:

某条非常喜歡看動畫，他會把看過的動畫都存到硬碟裡，這樣以後才可以再翻出來複習。

而習慣很不好的他，把動漫集數放的到處都是，但每一集都只會出現在一個硬碟裡，而且不會切割。

有一天，他突然很想看Tentacle Lover時，發現一個麻煩的問題。

動漫當然就是要從第一集開始一集集依序看完，但是不同集的動畫不一定放在同一個硬碟裡，因此要看完一部動畫可能會用到很多顆硬碟。

硬碟當然是要接上電腦才能用，但是電腦的USB接頭是有限的，因此可能沒有辦法一次把全部的硬碟接上去，所以當你看完一集時可能需要抽換硬碟才能看到下一集。

當然如果現在連在電腦上的硬碟已經有你要看的那一集那就可以不用換。因為一直換硬碟實在是太麻煩了，會影響看動畫的心情。

所以他把他想看的動畫存在哪一顆硬碟中依序跟你講，希望請你寫一個程式來決定怎麼抽換硬碟才能使抽換次數降到最低。

舉例來說，動畫可能依序放在1 2 3 1 3 1 2這三個硬碟中，電腦上有兩個USB接頭，最少需要兩次抽換才能看完整部動畫。

方法如下，首先先把1 2接上電腦，之後把2拔掉換成3，最後再把1 3之一拔掉換2，這樣就可以全部看完。

Input:Output:

每個輸入檔只有一筆測試資料。
第一列有三個正整數，n,k,p(1<=k<=n<=100,000；1<=p<=500,000)，n代表的是某条有的硬碟數量，k是USB接頭數，p是集數。
接下來有p列，依序代表動漫集數，每列有一個正整數，每個正整數介於1到n之間，代表要插入的硬碟編號。

請輸出某条最少要抽換幾次。

Sample Input:Sample Output:

3 2 7
1
2
3
1
3
1
2

Source:

POI 12 Stage 1

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	32768kb
1-ocen	1000ms	32768kb
1	1000ms	32768kb	10
2-ocen	1000ms	32768kb
2	1000ms	32768kb	10
3-ocen	1000ms	32768kb
3	1000ms	32768kb	10
4-ocen	1000ms	32768kb
4	1000ms	32768kb	10
5-ocen	1000ms	32768kb
5	1000ms	32768kb	10
6	2500ms	32768kb	10
7	2500ms	32768kb	10
8	2500ms	32768kb	10
9	2500ms	32768kb	10
10	2500ms	32768kb	10