Problem D
Bergur

Hot Yoga

Bergur hefur ákveðið að fara í Hot Yoga tíma til að brenna smá fitu. Bergi finnst ekki nógu flott að fara bara reglulega í Hot Yoga, hann ætlar sér einnig að vera lengur eða jafn lengi í Hot Yoga í dag og hann var síðastliðinn dag. Bergur ætlar semsagt að mæta í Hot Yoga tíma hvern einasta dag í næstu $N$ daga. Það er gefið fyrir hvern dag hvað er hægt að vera lengi í Hot Yoga, skilgreint sem $a_ i$ fyrir $i$-ta daginn. Þó er Bergi velkomið að vera styttra.

Bergi langar að vera sem lengst í Hot Yoga yfir þessa $N$ daga en samt uppfylla kröfuna um að vera alltaf jafn lengi eða lengur í Hot Yoga heldur en daginn áður.

Það er að segja, fjöldi tíma sem Bergur fer í Hot Yoga yfir hvern dag fer vaxandi.

Inntak

Fyrsta línan í inntakinu inniheldur eina heiltölu $N$ ($1 \leq N \leq 3 \cdot 10^5$), fjöldi daga.

Næsta lína inniheldur $N$ tölustafi $1 \leq a_ i \leq 10^4$ þar sem $i$-ta talan táknar hámark fjölda tíma sem Bergur má æfa á þeim degi.

Úttak

Skrifið út eina heiltölu, mestan fjölda tíma sem Bergur getur æft án þess að brjóta reglur sem voru skilgreindar að ofan.

Stigagjöf

10
5 6 7 8 9 3 2 7 8 9

38

3
3 2 1

3