1221 . 炒菜問題
TopCoder
Description
自從小當家得到了傳說中的八樣廚具之後，回到了他母親的店——楊泉酒家。
由於大家都愛看中華一番的漫畫，所以有很多人慕名前往楊泉酒家吃飯。
楊泉酒家的廚房總共有k個炒菜鍋，而客人可能點菜的種類有n種。
由於小當家每次只能炒一道菜，而且一定要按照客人點菜的順序炒，必須要精簡洗炒菜鍋的次數，這樣才能加快速度。
是這樣的，一旦這次炒菜使用的炒菜鍋，沒有被用過，或者上一道菜與這一道菜種類不同，炒菜前就必須叫四郎先洗鍋子。
要不然被老饕們發現下場會很慘的。
這可讓在廚房裡負責洗鍋子的四郎大傷腦筋了，心裡一直盤算著，到底最少只要洗幾次鍋子呢？
請你寫個程式來回答這個問題吧!
Input Format
每個輸入檔只有一筆測試資料。
第一列有三個正整數，n,k,p(1<=k<=n<=100,000；1<=p<=500,000)，其中p代表要炒的菜餚總共有幾道。
接下來有p列，依序代表上菜順序，每列有一個正整數，每個正整數介於1到n之間，代表要炒的菜餚編號。
Output Format
請輸出四郎至少要洗幾次鍋子。
Sample Input 1
3 2 7
1
2
3
1
3
1
2
1
2
3
1
3
1
2
Sample Output 1
4
Hints
| 菜餚編號 | 使用鍋子 | 是否洗鍋 |
| 1 | 1 | 是 |
| 2 | 2 | 是 |
| 3 | 2 | 是 |
| 1 | 1 | 否 |
| 3 | 2 | 否 |
| 1 | 1 | 否 |
| 2 | 1 | 是 |
※2008/2/17：輸入說明敘述修正。
Problem Source
原TIOJ1221 / TIOJ 2008例行賽03-Elite (prob C)。TPSC 2004初賽、POI 2004/2005 Stage I。Problem Setter：Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 6 |
| 2 | 1 | 6 |
| 3 | 2 | 6 |
| 4 | 3 | 6 |
| 5 | 4 | 6 |
| 6 | 5 | 6 |
| 7 | 6 | 6 |
| 8 | 7 | 6 |
| 9 | 8 | 6 |
| 10 | 9 | 6 |
| 11 | 10 | 6 |
| 12 | 11 | 6 |
| 13 | 12 | 6 |
| 14 | 13 | 6 |
| 15 | 14 | 6 |
| 16 | 15 | 10 |