5. Kamenná cesta

Táto úloha je prebraná z domáceho kola Olympiády v Informatike kategórie B. Riešením tejto úlohy sa teda viete zapojiť aj do Olympiády (odovzdať to však musíte samostatne druhýkrát).

Ak sa Vám úlohy v PRASKu páčia, vyskúšajte si aj riešenie Olympiády, termín jej domáceho kola je do 30. novembra 2019. Riešením domáceho kola máte možnosť postúpiť do kola krajského a skúsiť si riešenie aj v súťažnejších podmienkach a kratšom čase. Na postup na krajské kolo obvylke stačí 10 bodov, takže ak vyriešite túto úlohu a ešte niečo, postup budete mať zaručený.

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu conditions_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Andrejovi na [email protected]

Jitka sa rozhodla ísť pozrieť Ema do Švajčiarska. Ten sa na jej príchod veľmi tešil a pripravil pre ňu prekvapenie – romantický pobyt v horskej chate. Keď sa však už tretiu hodinu drali hustým lesom na ceste k chate, uvedomil si Emo, že ceny vo Švajčiarsku sú odlišné od tých na Slovensku. A tak za cenu priemerného slovenského ubytovania objednal Emo pomerne podpriemernú chatku uprostred ničoho.

Našťastie, to ich už našiel chatár, ktorý poznal zopár šikovných skratiek a o chvíľu už mali chatku na dohľad. Poslednú prekážku tvorila riečka, z ktorej vytŕčalo veľké množstvo kameňov, po ktorých sa dalo preskákať na druhú stranu. Blíži sa však obdobie dažďov a Emo je nervózny. Ako dlho potrvá, kým sa hladina zdvihne natoľko, že sa už nebude dať dostať na druhú stranu?

Úloha

V rieke sa nachádza cesta tvorená \(n\) kameňmi. Pre každý kameň máme zadané jedno číslo \(k_i\) – poradové číslo posledného dňa kedy je ešte tento kameň nezatopený a dá sa po ňom prejsť.

Pri prechode riekou môžeme samozrejme stúpať iba na nezaplavené kamene. Jedným krokom sa však vieme presunúť nielen na nasledujúci kameň, ale aj na kameň hneď za ním. Vďaka tomu je možné niektoré zaplavené kamene prekročiť.

Vašou úlohou je zistiť, ktorý najneskorší deň sa ešte stále dá dostať z jednej strany rieky na druhý.

Formát vstupu

Na prvom riadku vstupu je číslo \(n\) \((2\leq n\leq 1\,000\,000)\) – počet kameňov v rieke, ktoré tvoria cestu medzi dvoma brehmi.

Na druhom riadku vstupu je \(n\) medzerami oddelených čísel \(k_1, k_2 \dots k_n\). Hodnota \(k_i\) \((1\leq k_i\leq 1\,000\,000\,000)\) označuje posledný deň v ktorý sa bude dať prejsť po \(i\)-tom kameni predtým ako bude zatopený.

Formát výstupu

Na výstup vypíšte jediné číslo \(x\) – posledný deň kedy sa dá prejsť po nezatopených kameňoch z jednej strany rieky na druhú.

Hodnotenie

Sú 3 sady vstupov po 5 bodov. Pre prvú sadu naviac platí, že \(n \leq 1\,000\).

Príklad

Input:

7
7 3 15 7 2 8 6

Output:

7

V 7. deň je zatopený druhý, štvrtý a siedmy kameň, teda tie, ktoré majú ako deň zatopenia číslo menšie ako 7. Pomocou nezatopených kameňov sa dá však stále popreskakovať na druhú stranu rieky. Stačí skočit z brehu na prvý kameň, odtiaľ preskočiť na tretí kameň, posunúť sa na štvrtý, z neho na šiesty a odtiaľ už rovno na druhý breh. Všimnite si, že pri každom skoku, vrátane tých z brehu a na breh, sme preskočili maximálne jeden kameň. V ôsmy deň už nemôžme použiť prvý ani druhý kameň a teda z brehu nevieme skočiť na nezatopený kameň.