Počet bodov:
Popis:  12b
Program:  8b

Záhradník rád záhradníčil, pestoval ovocie a zeleninu a užíval si pokojný život. Táto idylka však skončila, keď jedného dňa na Záhradníkovu hlavu vyskočil Krtko a začal Záhradníka ovládať. Záhradník sa už viac nestaral o baklažány, kaleráby, jablká, ananásy či petržleny a namiesto toho kopal krtince a organizoval sústredenia. A hoci už nemal viac v živote pokoja, aspoň robil radosť mnohým deťom, ktoré sa na sústredenia veľmi tešili.

Ani táto radosť však netrvala dlho, lebo Záhradníkove schopnosti sa rozhodla využiť aj hlavná kubrická ploštica. Tej bolo smutno, že ploštice kvôli svojej zlej reputácii medzi ľuďmi klesajú na počtoch a rozhodla sa proti tomuto trendu bojovať a pre ostatné ploštice zorganizovať speed dating. Vyskočila na hlavu Krtkovi, ktorý sedel na hlave Záhradníkovi a začala ho ovládať, aby jej speed dating pripravil.

Speed dating ploštíc prebieha následovne. Máme \(n\) ploštíc a každá dvojica z nich pôjde na rande na večeru. Večerať budú účastníkov sústredenia a každá ploštica si na svojho účastníka počká v jednej z dvoch postelí na izbe. No každá ploštica má rada iný typ posteľných obliečok a chce byť iba v posteli s tými obliečkami. Tie bude Záhradník ovládaný Krtkom ovladaný kubrickou plošticou medzi jednotlivými rande v prípade potreby prezliekať. Toto sťažuje fakt, že postele v izbe sú rôzne veľké, čo plošticiam síce neprekáža, no znamená to, že treba kúpiť iný rozmer obliečky na jednu posteľ, a iný na druhú.

Kubrická ploštica potrebuje nakázať Krtkovi, nech nakáže Záhradníkovi koľko kusov obliečok treba nakúpiť, nech každá dvojica z jej \(n\) ploštíc môže spolu ísť na rande.

Úloha

Pre daný počet ploštíc a ich preferencie zistite minimálny počet obliečok, ktoré treba nakúpiť na sústredenie, aby každá dvojica ploštíc mohla ísť spolu na rande, každá do inej postele s jej obľúbeným typom obliečok. Ak na speed dating príde iba jedna ploštica, pôjde sa navečerať osamote (a spoznať sa sama so sebou).

Formát vstupu

V prvom riadku vstupu sú čísla \(n\) a \(k\) (\(1 \leq n,k \leq 2 \cdot 10^5\)) udávajúce počet ploštíc a počet rôznych typov obliečok.

V druhom riadku následuje \(n\) čísel, \(p_1, p_2, \cdots, p_n\) kde \(p_i\) je preferovaný typ obliečok \(i\)-tej ploštice.

Sú dve sady. Pre prvú sadu platí, že \(p_i\) sa rovná \(i\).

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo - počet kusov obliečok, ktoré treba nakúpiť.

Príklady

Input:

5 5
1 2 3 4 5

Output:

8

Aj keď každú obliečku chce iba jedna ploštica, aj tak musíme z niektorých typov kúpiť dva kusy. Keby sme napríklad kúpili obliečku typu 4 a 5 len v rozmeroch prvej postele, keď pôjdu ploštice 4 a 5 na rande, nebudeme vedieť obliecť druhú posteľ tak, aby ju niektorá z nich chcela. Rozmyslite si, ktoré obliečky stačí kúpiť pre obe postele, aby nám ich stačilo dokopy 8 kusov.

Input:

6 4
1 2 3 2 3 2

Output:

5

Záhradník potrebuje kúpiť obliečky typu 2 a 3 pre obe postele, a obliečku typu 1 len pre jeden rozmer. Bez ohľadu na to, ktoré dve ploštice pôjdu na rande, budeme každej vedieť obliecť posteľ do jej obľúbenej obliečky.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.