Zadanie

Ideme po poli

Počet bodov: 40

V ďalekej budúcnosti, v roku 2047, vynašli vedci nový spôsob dopravy. Ide o tzv. auto na diskrétny pohon. Cestovanie takýmto autom nestojí vôbec nič, ale má svoje obmedzenia. Napríklad takú rýchlosť nemôže zmeniť len tak kedykoľvek. S úderom každej sekundy ju môže zvýšiť o \(1\), znížiť o \(1\), alebo ponechať rovnakú.

Niektoré pravidlá cestnej premávky sa ešte nestihli prispôsobiť tomuto novému spôsobu dopravy. Stále sú oblasti, cez ktoré jednoducho nemôžete íst príliš rýchlo. Zistiť, ako najrýchlejšie sa viete dostať z jedného miesta na druhé, môže byť pomerne náročné. Preto to teraz dostávate na úlohu vy!

Úloha

Cestu si rozdelíme na \(n\) bodov uložených na jednej priamke, susedné dva body majú vzdialenosť presne \(1\). V každom bode je určená maximálna rýchlosť. Treba ju dodržať buď, keď do bodu vchádzame, alebo keď z neho vychádzame (nie nutne oboje). Napríklad ak má bod maximálnu rýchlosť \(5\), môžeme doňho prísť rýchlosťou \(5\) a výjsť rýchlosťou \(6\), alebo prísť rýchlosťou \(6\) a výjsť rýchlosťou \(5\), ale nemôžeme príjsť aj výjsť rýchlosťou \(6\).

Špeciálny význam bude mať hodnota \(0\), ktorá znamená, že v danom bode musíme aspoň sekundu úplne stáť.

Vašou úlohou je zistiť, ako najrýchlejšie sa vieme dostať z prvého bodu do posledného bodu tak, že začíname s nulovou rýchlosťou a taktiež skončíme s nulovou rýchlosťou a máme dovolené hýbať sa iba dopredu.

Vstup a výstup

Na prvom riadku je číslo \(n\), (\(2 \leq n \leq 50\,000\)). Na druhom riadku je \(n\) čísel \(x_i\), (\(0 \leq x_i \leq 10^9\)), \(i\)-te z nich vyjadruje obmedzenie rýchlosti v \(i\)-tom bode.

Na výstup vypíšte jediné celé číslo, počet sekúnd, koľko trvá najrýchlejšia cesta z prvého bodu do posledného.

Pozor, časový limit je pomerne tesný, optimálne programy v pomalších jazykoch, ako aj rozšafné programy v rýchlejších, pravdepodobne zopár bodov stratia.

Príklad

Input:

10
1 2 3 4 5 6 7 8 9 10

Output:

5

Rozpis po sekundách:

1. Rýchlosťou 1 prejdeme z prvého bodu do druhého.

2. Rýchlosťou 2 prejdeme z druhého bodu do štvrtého.

3. Rýchlosťou 3 prejdeme zo štvrtého bodu do siedmeho.

4. Rýchlosťou 2 prejdeme zo siedmeho bodu do deviateho.

5. Rýchlosťou 1 prejdeme z deviateho bodu do cieľového desiateho.

Input:

4
1 0 0 1

Output:

5

Po prvej sekunde sa dostaneme do druhého bodu, druhú sekundu v ňom stojíme. Tretiu sekundu sa dostaneme do tretieho bodu, štvrtú sekundu v ňom stojíme. Nakoniec v piatej sekunde sa dostaneme do posledného bodu, v ktorom na jej konci zastavíme.

Input:

10
0 1 2 2 3 3 2 2 1 0

Output:

5

Môžeme si dovoliť ísť presne rovnako, ako v prvom ukážkovom vstupe. Napríklad druhý bod má síce obmedzenie rýchlosti \(1\), ale keďže doňho prichádzame rýchlosťou \(1\), odísť z neho môžeme kľudne aj rýchlosťou \(2\).

Input:

10
0 1 2 3 2 2 3 2 1 0

Output:

6

V tomto prípade nemôžeme postupovať ako v prvom, lebo v rýchlosti \(3\) by sme prešli až cez dva body (piaty a šiesty) s obmedzením rýchlosti na \(2\). Pôjdeme teda nasledovne (opäť rozpis po sekundách):

1. Rýchlosťou 1 prejdeme z prvého bodu do druhého.

2. Rýchlosťou 2 prejdeme z druhého bodu do štvrtého.

3. Rýchlosťou 2 prejdeme zo štvrtého bodu do šiesteho.

4. Rýchlosťou 2 prejdeme zo šiesteho bodu do ôsmeho.

5. Rýchlosťou 1 prejdeme z ôsmeho bodu do deviateho.

6. Rýchlosťou 1 prejdeme z deviateho bodu do cieľového desiateho.