6. Dijkstra inak

Danovi sa začal nový semester a to preňho znamená jediné. Blíži sa skúškové. Z knižnice si už požičal všetky skriptá a cvičebnice. Keďže si po ne bol už o šiestej ráno v prvý výpožičný deň, ušli sa mu dokonca tie najlepšie kusy. Čo sa jeho spolužiakov týka, tí už také šťastie nemali a knižky sa im neušli. Aby znova polovica ročníka nevyletela, rozhodol sa dobrotivo požičať svoje vzdelávacie materiály na naskenovanie.

Vieme si však predstaviť, že naskenovať tie tisíce strán chvíľu potrvá a Dano každú sekundu čo v ruke nemá svoje skriptá pociťuje fyzickú bolesť. Krtkovi obzvlášť nebolo príjemné pozerať sa ako sa zvíja na zemi a tak spravil náčrty PCBčiek potrebných na zostavenie robota, ktorý skenovanie zautomatizuje, urýchli a spraralelizuje. Náčrty však vôbec nie sú pekné, vodiče idú krížom krážom, masívne sa križujú a nikto sa v tom nevyzná. Aby nedošlo ku skratom, bude treba viacvrstvové dosky.

Na odhad ceny robota (a teda finálne rozhodutie či radšej nenecháme Dana trpieť) budeme potrebovať vedieť, koľko najmenej vrstiev môžu mať dosky bez toho aby sa vodiče križovali. Keďže toto je úloha v KSP, je na vás aby ste to zistili.

Úloha

Náčrt má \(N\) vodičov. Každý vodič má 2 konce a všetky konce vodičov sú rozdelné do 2 stĺpcov (ľavého a pravého) po \(N\) koncoch. Konce v oboch stĺpcoch sú očíslované zhora nadol od 1 po \(N\). Dva vodiče sa križujú ak sú na tej istej vrstve a ak jeden vodič má číslo ľavého konca menšie ako číslo ľavého konca druhého vodiča a číslo pravého konca väčšie ako číslo pravého konca druhého vodiča. Každý vodič sa môže nachádzať na práve jednej vrstve.

Na prvom riadku je celé číslo \(N\) (\(0 \leq N \leq 10^6\)) - počet vodičov. Na druhom riadku je \(N\) rôznych celých čísel. Nech \(i\)-te z nich je \(v_i\), potom \(i\)-ty vodič spája \(i\)-ty koniec v ľavom stĺpci s \(v_i\)-tým koncom v pravom stĺpci.

Na výstup vypíšte jeden riadok s jedným celým číslom - najmenším počtom vrstiev postačujúcich na zostavenie dosky bez križovaní.

Hodnotenie

Sú 4 sady vstupov. Platia v nich nasledovné obmedzenia:

Príklady

Input:

3
1 2 3

Output:

1

Input:

5
5 4 3 2 1

Output:

5

Input:

6
4 5 2 3 1 6

Output:

3