Hide

Problem K
Bergur

Languages en is
/problems/bergur/file/statement/is/img-0001.jpg
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

Hópur

Stig

Takmarkanir

1

50

$N \leq 1\, 000$

2

50

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
10
5 6 7 8 9 3 2 7 8 9
38
Sample Input 2 Sample Output 2
3
3 2 1
3