4. Štrádovanie si

Ján Ploštica sa spolu s rodinou nedávno presťahoval do mesta Gaučislava. Je to novozaložená kolónia ploštíc v T2, ktorá láka na pestrú a súdržnú susedskú komunitu, ale aj ľahkú dostupnosť služieb a občianskeho vybavenia, či prepracovanú a udržiavanú sieť tunelov. Celá navyše leží v príjemnom prostredí molitánu, ktorý plošticiam poskytuje zdravé a podnetné prostredie pre napĺňajúci každodenný život.

Pri návrhu komunikácií sa ploštičím inžinierom podarilo naplánovať mesto bez jedinej zbytočnej cesty – medzi každými dvoma miestami v Gaučislave sa dá dostať práve jedným spôsobom, pokiaľ sa ploštice po ceste nevracajú späť. Zároveň každá lokácia v meste má presne podľa plánu zaznačenú nadzemnú výšku, v ktorej sa nachádza, v jednotkách nožičkomilióntiny (nm). S rôznymi nadzemnými výškami sa totiž spájajú rozdielne podmienky, ktoré rozličným plošticiam vyhovujú rozdielnym spôsobom. Tým si ale lámať hlavu nemusíme, pretože to už predsa inžinieri vyriešili a navrhli.

Ján P. by sa rád pochválil svojim ploštičím kamarátom tým, aké veľké je mesto, kam sa presťahoval. Preto sa vydal na prechádzku tunelmi od svojho domu, a pri každej budove, ktorú minul, si poznačil jej nadzemnú výšku. Je si pritom istý, že sa mu podarilo navštíviť každé miesto v Gaučislave.

Dostal tak postupnosť výšok, ktorú ukázal kamarátom. Tí ale namietali, že ak navštívil nejaké miesto veľakrát, tak v zápise sa tiež vyskytlo veľakrát, a teda sa bude zdať, že Gaučislava je väčšia, než v skutočnosti. Preto potrebuje zistiť, aké najmenšie mesto môže byť, aby ich presvedčil, že určite musí byť masívne.

Úloha

Trochu formálnejšie, mesto Gaučislava tvorí strom – neorientovaný súvislý acyklický graf. To znamená, že medzi každými dvoma vrcholmi vedie práve jedna cesta (postupnosť vrcholov a hrán, v ktorej sa žiadny vrchol ani hrana neopakuje). Každý vrchol má svoju určenú výšku v nm, v rozsahu \(0\) až \(10^9\) (zhruba výška gauča aj s operadlom). Rôzne vrcholy môžu mať rovnakú výšku.

Dostanete číslo \(n\) a postupnosť výšok navštívených vrcholov \(v_1 ... v_n\). Vašou úlohou je vypísať najmenšie číslo \(m \leq n\) také, že existuje strom s \(m\) vrcholmi nejakých výšok, ktorého prechádzaním vieme dostať zadanú postupnosť výšok, pričom si zapisujeme každý vrchol, na ktorý vstúpime (a ten istý vrchol nevieme zapísať znova bez toho, aby sme z neho najskôr odišli a vrátili sa).

Formát vstupu

Na prvom riadku dostanete číslo \(n\) – počet zaznamenaných výšok. Na druhom riadku dostanete \(n\) čísel v rozsahu \(\langle 0, 10^9 \rangle\) – postupnosť výšok navštívených vrcholov.

Formát výstupu

Vypíšte jedno číslo \(m\) spĺňajúce zadanie – najmenší možný počet vrcholov stromu.

Obmedzenia

Sú \(4\) sady vstupov po \(2\) body. Platia v nich nasledovné obmedzenia:

Príklad

Input:

4
4 20 4 20

Output:

2

Naozaj masívne mesto, ktoré obsahuje dva domy s výškami 4 a 20. Videli ste hádam niekedy väčšie ploštičie mesto?

Input:

8
4 20 20 4 4 4 20 10

Output:

6

Prvých 5 výšok je síce podobných, no popisujú rôzne budovy. Šiesta výška popisuje štvrtú budovu, siedma tretiu, ôsma predtým nenavštívenú šiestu, ktorá susedí s tretiou.