Verkefnalýsing

Japanski eyjaklasinn er langur og mjór eyjaklasi. Japanska eyjaklasanum er skipt í $N$ hluta með samsíða markalínum. Hlutarnir eru númeraðir í röð frá $1$ til $N$ frá öðrum endanum. Hæð hluta $i$ ($1 \le i \le N$) er $A_i$.

Japanski eyjaklasinn er umkringdur hafi og sjávarborðið er fast óháð staðsetningu. Hluti sem hefur hæð sem er strangt hærri en sjávarborðið kallast þurrlendi.

Samfelldur hluti þurrlendis kallast eyja. Nákvæmar tiltekið: Fyrir heiltölur $l$, $r$ ($1 \le l \le r \le N$) kallast sá hluti japanska eyjaklasans sem samanstendur af hluta $l$, hluta $l+1$, $\dots$, hluta $r$ svæði $[l, r]$. Svæði $[l, r]$ sem uppfyllir eftirfarandi skilyrði kallast eyja:

• Hluti $l$, hluti $l+1$, $\dots$, hluti $r$ eru allir þurrlendi.
• Ef $l > 1$, þá er hluti $l-1$ ekki þurrlendi.
• Ef $r < N$, þá er hluti $r+1$ ekki þurrlendi.

Vegna hækkandi sjávarborðs er japanski eyjaklasinn að sökkva smám saman. Núverandi hæð sjávarborðs er $0$, en hún hækkar smám saman með tímanum þar til allt Japan verður loks að hafi.

JOI tók eftir því að þegar sjávarborðið hækkar þá fjölgar og fækkar eyjum í Japan. Finndu mesta fjölda eyja á tímabilinu frá núinu þar til ekkert þurrlendi er eftir í Japan (núið meðtalið).

Skorður

• $1 \le N \le 100000 (= 10^5)$
• $0 \le A_i \le 1000000000 (= 10^9)$ ($1 \le i \le N$)

Inntak / Úttak

Inntak
Inntakið er gefið úr staðalinntaki á eftirfarandi sniði:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Úttak
Prentið í $1$ línu mesta fjölda eyja á tímabilinu frá núinu þar til ekkert þurrlendi er eftir í Japan (núið meðtalið).

Undirverkefni

1. ($7$ stig) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ stig) $N \le 2000$
3. ($85$ stig) Engar viðbótarskorður.

Dæmi um inntak / úttak

Dæmi um inntak 1

6
0 1 2 1 3 2

Dæmi um úttak 1

2

• Þegar hæð sjávarborðs er að minnsta kosti $0$ og minni en $1$ eru hlutar $2, 3, 4, 5, 6$ þurrlendi. Þar sem svæði $[2, 6]$ er eina eyjan er fjöldi eyja $1$.
• Þegar hæð sjávarborðs er að minnsta kosti $1$ og minni en $2$ eru hlutar $3, 5, 6$ þurrlendi. Þar sem svæði $[3, 3]$ og svæði $[5, 6]$ eru eyjar er fjöldi eyja $2$.
• Þegar hæð sjávarborðs er að minnsta kosti $2$ og minni en $3$ er aðeins hluti $5$ þurrlendi. Þar sem svæði $[5, 5]$ er eina eyjan er fjöldi eyja $1$.
• Þegar hæð sjávarborðs nær $3$ er ekkert þurrlendi eftir og fjöldi eyja verður $0$.

Þess vegna er mesti fjöldi eyja $2$, svo prentað er $2$.

Dæmi um inntak 2

6
3 2 3 0 2 0

Dæmi um úttak 2

2

• Þegar hæð sjávarborðs er að minnsta kosti $0$ og minni en $2$ eru hlutar $1, 2, 3, 5$ þurrlendi. Þar sem svæði $[1, 3]$ og svæði $[5, 5]$ eru eyjar er fjöldi eyja $2$.
• Þegar hæð sjávarborðs er að minnsta kosti $2$ og minni en $3$ eru hlutar $1, 3$ þurrlendi. Þar sem svæði $[1, 1]$ og svæði $[3, 3]$ eru eyjar er fjöldi eyja $2$.
• Þegar hæð sjávarborðs nær $3$ er ekkert þurrlendi eftir og fjöldi eyja verður $0$.

Þess vegna er mesti fjöldi eyja $2$, svo prentað er $2$.

Dæmi um inntak 3

10
4 1 2 1 2 3 5 4 3 2

Dæmi um úttak 3

3