Problembeskrivning

Den japanska ögruppen är en lång och smal ögrupp. Den japanska ögruppen är indelad i $N$ sektioner av parallella gränslinjer. Sektionerna är numrerade i ordning från $1$ till $N$ från ena änden. Höjden på sektion $i$ ($1 \le i \le N$) är $A_i$.

Den japanska ögruppen är omgiven av hav, och havsnivån är konstant oberoende av plats. En sektion vars höjd är strikt högre än havsnivån kallas land.

En sammanhängande del av land kallas en ö. Mer precist gäller följande: För heltal $l$, $r$ ($1 \le l \le r \le N$) kallas den del av den japanska ögruppen som består av sektion $l$, sektion $l+1$, $\dots$, sektion $r$ för område $[l, r]$. Ett område $[l, r]$ som uppfyller följande villkor kallas en ö:

• Sektion $l$, sektion $l+1$, $\dots$, sektion $r$ är alla land.
• Om $l > 1$ är sektion $l-1$ inte land.
• Om $r < N$ är sektion $r+1$ inte land.

På grund av stigande havsnivåer sjunker den japanska ögruppen lite i taget. Den nuvarande havsnivån är $0$, men den stiger gradvis med tiden tills hela Japan till slut blir hav.

JOI lade märke till att när havsnivån stiger så ökar och minskar antalet öar i Japan. Bestäm det största antalet öar under perioden från nutid fram till dess att det inte finns något land kvar i Japan (inklusive nutid).

Begränsningar

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

Indata / Utdata

Indata
Indatan ges från standardindata i följande format:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Utdata
Skriv på $1$ rad ut det största antalet öar under perioden från nutid fram till dess att det inte finns något land kvar i Japan (inklusive nutid).

Deluppgifter

1. ($7$ poäng) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ poäng) $N \le 2000$
3. ($85$ poäng) Inga ytterligare begränsningar.

Exempel på indata / utdata

Exempelindata 1

6
0 1 2 1 3 2

Exempelutdata 1

2

• När havsnivån är minst $0$ och mindre än $1$ är sektionerna $2, 3, 4, 5, 6$ land. Eftersom område $[2, 6]$ är den enda ön är antalet öar $1$.
• När havsnivån är minst $1$ och mindre än $2$ är sektionerna $3, 5, 6$ land. Eftersom område $[3, 3]$ och område $[5, 6]$ är öar är antalet öar $2$.
• När havsnivån är minst $2$ och mindre än $3$ är endast sektion $5$ land. Eftersom område $[5, 5]$ är den enda ön är antalet öar $1$.
• När havsnivån når $3$ finns det inget land kvar och antalet öar blir $0$.

Det största antalet öar är alltså $2$, så skriv ut $2$.

Exempelindata 2

6
3 2 3 0 2 0

Exempelutdata 2

2

• När havsnivån är minst $0$ och mindre än $2$ är sektionerna $1, 2, 3, 5$ land. Eftersom område $[1, 3]$ och område $[5, 5]$ är öar är antalet öar $2$.
• När havsnivån är minst $2$ och mindre än $3$ är sektionerna $1, 3$ land. Eftersom område $[1, 1]$ och område $[3, 3]$ är öar är antalet öar $2$.
• När havsnivån når $3$ finns det inget land kvar och antalet öar blir $0$.

Det största antalet öar är alltså $2$, så skriv ut $2$.

Exempelindata 3

10
4 1 2 1 2 3 5 4 3 2

Exempelutdata 3

3