Järjestamine

문제

Nimetame arvujada $A_1,A_2,\dots ,A_{N}A\_1,\; A\_2,\; \backslash dots,\; A\_N$ järjestatuks, kui iga korral kehtib $A_i\le A_{i+1}A\_i\; \backslash le\; A\_\{i+1\}$.

Vaatleme järgmist meetodit arvujada järjestamiseks: kõigepealt tükeldatakse jada $MM$ lõiguks (jada esimesed $k_{1}k\_1$ elementi moodustavad ühe lõigu, järgmised $k_{2}k\_2$ elementi teise j.n.e kuni viimased $k_{M}k\_M$ elementi moodustavad viimase lõigu) ja edasi tohib omavahel vahetada terveid lõike, aga mitte muuta elementide järjekorda ühegi lõigu sees.

On selge, et mõnede lõikudeks jaotuste korral on jada järjestamine lõikude vahetamise teel võimalik (kindlasti saab iga $NN$-elemendilise jada järjestada selle $NN$ lõiguks tükeldamise järel) ja mõnede korral ei ole (näiteks üheks lõiguks "tükeldamisel" ei saa järjestada ühtki jada, mis pole juba algselt järjestatud).

Kirjutada programm, mis leiab antud jada jaoks vähima arvu $MM$, mille korral leidub selline jada tükeldus $MM$ lõiguks, et terve jada saab lõikude vahetamise teel järjestada.

입력

Tekstifaili esimesel real on jada elementide arv $NN$ ($1\le N\le 5000001\; \backslash le\; N\; \backslash le\; 500\backslash ,000$) ja teisel real $NN$ tühikutega eraldatud täisarvu: jada elemendid $A_{i}A\_i$ ($1\le A_i\le N1\; \backslash le\; A\_i\; \backslash le\; N$).

출력

Tekstifaili ainsale reale väljastada üks täisarv: minimaalne lõikude arv, milleks peab jada tükeldama, et selle saaks lõikude vahetamise teel järjestada.