Problem B
Tvätt-Lina

Lina har precis tvättat och har hängt upp $N$ stycken strumpor på en tvättlina. Det finns strumpor i $C$ olika färger och Lina är väldigt noggrann med att strumporna ska paras ihop efter färg. Nu är det dags att samla ihop strumporna, men då det är väldigt många strumpor kan hon inte bära alla på samma gång. Hon skulle såklart kunna gå kors och tvärs bland strumporna och para ihop några i taget men Lina är väldigt lat och tycker att det verkar jobbigt. Därför använder hon istället sin snabb-sorteringsstrategi.

Den fungerar enligt följande: Hon tar en IKEA-kasse där det får plats $M$ strumpor och går från vänster till höger längs med tvättlinan. Varje gång hon plockar en ny strumpa från linan kan hon antingen välja att para ihop den med en av strumporna i IKEA-kassen (och paret hamnar **inte** i kassen då) eller så kan hon lägga ned den nya strumpan i kassen. Om kassen är full måste hon slänga bort en av strumporna hon redan har för att få plats med den nya, annars tvingas hon slänga bort den nya strumpan. Hur många strumpor kan Lina maximalt para ihop med sin strategi?

Indata

Den första raden innehåller tre heltal, $N$, $M$, $C$ $(2 \leq N \leq 10^5), (1 \leq M,C \leq N)$. $N$ är antalet strumpor på tvättlinan, $M$ är antalet strumpor som får plats i IKEA-kassen, och $C$ är antalet olika färger strumporna kan ha.

Därefter kommer en rad som innehåller $N$ heltal som beskriver färgen av strumporna som hänger på tvättlinan, tal $n_i$ $(1 \leq n_i \leq C)$ betyder att den $i$:te strumpan har färg $n_i$.

Utdata

Skriv ut ett heltal, det maximala antalet par av strumpor som Lina kan skapa.

Poängsättning

Din lösning kommer att testas på flera olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring

I det första exempelfallet kan man först lägga sockorna med färg 2,3 och 3 i kassen. Sedan parar man ihop de med färg 3. Då har man en socka med färg 2 kvar i kassen. Därefter lägger man ned sockarna med färg 2 och 1 i kassen och parar ihop de med färg 2 så att man har en socka med färg 1 kvar i kassen. Tillsist kan man lägga ned den sista sockan med färg 1 i kassen och para ihop dem. Totalt blir det tre par av strumpor.

I det andra exempelfallet får det bara plats en strumpa i kassen. Först lägger man ned strumpan med färg 2 i kassen. Sedan kommer man till strumpan med färg 1. Eftersom kassen är full måste vi slänga bort någon strumpa. Om man slänger bort strumpan med färg 2 kan man lägga ned strumpan med färg 1 och därefter plocka upp nästa strumpa som också har färg 1 och para ihop den med strumpan i kassen. Det är det enda paret vi kan få så därför är svaret ett.

6 3 3
2 3 3 2 1 1

3

4 1 3
1 2 1 3

1

8 4 2
1 1 2 1 2 1 1 1

4