Problembeskrivelse

Den japanske øygruppen er en lang og smal øygruppe. Den japanske øygruppen er delt inn i $N$ seksjoner av parallelle grenselinjer. Seksjonene er nummerert i rekkefølge fra $1$ til $N$ fra den ene enden. Høyden til seksjon $i$ ($1 \le i \le N$) er $A_i$.

Den japanske øygruppen er omgitt av hav, og havnivået er konstant uavhengig av sted. En seksjon med høyde strengt større enn havnivået kalles land.

En sammenhengende del med land kalles en øy. Mer presist gjelder følgende: For heltall $l$, $r$ ($1 \le l \le r \le N$) kalles den delen av den japanske øygruppen som består av seksjon $l$, seksjon $l+1$, $\dots$, seksjon $r$ for område $[l, r]$. Et område $[l, r]$ som oppfyller følgende betingelser, kalles en øy:

• Seksjon $l$, seksjon $l+1$, $\dots$, seksjon $r$ er alle land.
• Hvis $l > 1$, er seksjon $l-1$ ikke land.
• Hvis $r < N$, er seksjon $r+1$ ikke land.

På grunn av stigende havnivå synker den japanske øygruppen litt etter litt. Det nåværende havnivået er $0$, men det stiger gradvis over tid, helt til hele Japan til slutt blir til hav.

JOI la merke til at etter hvert som havnivået stiger, øker og minker antallet øyer i Japan. Finn det maksimale antallet øyer i perioden fra nå og frem til det ikke er noe land igjen i Japan (inkludert nå).

Begrensninger

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

Inndata / Utdata

Inndata
Inndataen gis fra standard inndata i følgende format:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Utdata
Skriv ut på $1$ linje det maksimale antallet øyer i perioden fra nå og frem til det ikke er noe land igjen i Japan (inkludert nå).

Deloppgaver

1. ($7$ poeng) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ poeng) $N \le 2000$
3. ($85$ poeng) Ingen ytterligere begrensninger.

Eksempler på inndata / utdata

Eksempelinndata 1

6
0 1 2 1 3 2

Eksempelutdata 1

2

• Når havnivået er minst $0$ og mindre enn $1$, er seksjonene $2, 3, 4, 5, 6$ land. Siden område $[2, 6]$ er den eneste øya, er antallet øyer $1$.
• Når havnivået er minst $1$ og mindre enn $2$, er seksjonene $3, 5, 6$ land. Siden område $[3, 3]$ og område $[5, 6]$ er øyer, er antallet øyer $2$.
• Når havnivået er minst $2$ og mindre enn $3$, er bare seksjon $5$ land. Siden område $[5, 5]$ er den eneste øya, er antallet øyer $1$.
• Når havnivået når $3$, er det ikke noe land igjen, og antallet øyer blir $0$.

Derfor er det maksimale antallet øyer $2$, så vi skriver ut $2$.

Eksempelinndata 2

6
3 2 3 0 2 0

Eksempelutdata 2

2

• Når havnivået er minst $0$ og mindre enn $2$, er seksjonene $1, 2, 3, 5$ land. Siden område $[1, 3]$ og område $[5, 5]$ er øyer, er antallet øyer $2$.
• Når havnivået er minst $2$ og mindre enn $3$, er seksjonene $1, 3$ land. Siden område $[1, 1]$ og område $[3, 3]$ er øyer, er antallet øyer $2$.
• Når havnivået når $3$, er det ikke noe land igjen, og antallet øyer blir $0$.

Derfor er det maksimale antallet øyer $2$, så vi skriver ut $2$.

Eksempelinndata 3

10
4 1 2 1 2 3 5 4 3 2

Eksempelutdata 3

3