TopCoder

User's AC Ratio

96.3% (26/27)

Submission's AC Ratio

30.0% (39/130)

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

3 2 7
1
2
3
1
3
1
2

Sample Output

4

Hints

菜餚編號使用鍋子是否洗鍋
11
22
32
11
32
11
21

※2008/2/17:輸入說明敘述修正。

Problem Source

原TIOJ1221 / TIOJ 2008例行賽03-Elite (prob C)。TPSC 2004初賽、POI 2004/2005 Stage I。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 6
For Testdata: 1 ~ 1, Score: 6
For Testdata: 2 ~ 2, Score: 6
For Testdata: 3 ~ 3, Score: 6
For Testdata: 4 ~ 4, Score: 6
For Testdata: 5 ~ 5, Score: 6
For Testdata: 6 ~ 6, Score: 6
For Testdata: 7 ~ 7, Score: 6
For Testdata: 8 ~ 8, Score: 6
For Testdata: 9 ~ 9, Score: 6
For Testdata: 10 ~ 10, Score: 6
For Testdata: 11 ~ 11, Score: 6
For Testdata: 12 ~ 12, Score: 6
For Testdata: 13 ~ 13, Score: 6
For Testdata: 14 ~ 14, Score: 6
For Testdata: 15 ~ 15, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144
5 10000 65536 262144
6 10000 65536 262144
7 10000 65536 262144
8 10000 65536 262144
9 10000 65536 262144
10 10000 65536 262144
11 10000 65536 262144
12 10000 65536 262144
13 10000 65536 262144
14 10000 65536 262144
15 10000 65536 262144