TopCoder

Thumb opengraph icon 200x200
Kevin_Zhang
\(I\ want\ to\ be\ better!\ But\ how.....\)

User's AC Ratio

96.8% (30/31)

Submission's AC Ratio

25.9% (45/174)

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10
10 10000 65536 262144 11
11 10000 65536 262144 12
12 10000 65536 262144 13
13 10000 65536 262144 14
14 10000 65536 262144 15
15 10000 65536 262144 16