Description du problème

L'archipel japonais est un archipel long et étroit. Il est divisé en $N$ sections par des lignes frontières parallèles. Les sections sont numérotées de $1$ à $N$ dans l'ordre à partir d'une extrémité. L'altitude de la section $i$ ($1 \le i \le N$) est $A_i$.

L'archipel japonais est entouré par la mer, et le niveau de la mer est constant quel que soit l'endroit. Une section dont l'altitude est strictement supérieure au niveau de la mer est appelée terre.

Une partie continue de terre est appelée une île. Plus précisément, pour des entiers $l$, $r$ ($1 \le l \le r \le N$), la partie de l'archipel japonais constituée de la section $l$, de la section $l+1$, $\dots$, et de la section $r$ est appelée la région $[l, r]$. Une région $[l, r]$ vérifiant les conditions suivantes est appelée une île :

• La section $l$, la section $l+1$, $\dots$, la section $r$ sont toutes des terres.
• Si $l > 1$, alors la section $l-1$ n'est pas une terre.
• Si $r < N$, alors la section $r+1$ n'est pas une terre.

En raison de la montée du niveau de la mer, l'archipel japonais s'enfonce peu à peu. Le niveau actuel de la mer est $0$, mais il monte progressivement avec le temps, jusqu'à ce que tout le Japon soit recouvert par la mer.

JOI a remarqué qu'à mesure que le niveau de la mer monte, le nombre d'îles au Japon augmente et diminue. Trouvez le nombre maximum d'îles au cours de la période allant d'aujourd'hui jusqu'au moment où il n'y aura plus aucune terre au Japon (aujourd'hui inclus).

Contraintes

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

Entrée / Sortie

Entrée
L'entrée est fournie depuis l'entrée standard sous le format suivant :
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Sortie
Affichez sur $1$ ligne le nombre maximum d'îles au cours de la période allant d'aujourd'hui jusqu'au moment où il n'y aura plus aucune terre au Japon (aujourd'hui inclus).

Sous-tâches

1. ($7$ points) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ points) $N \le 2000$
3. ($85$ points) Aucune contrainte supplémentaire.

Exemples d'entrée / sortie

Exemple d'entrée 1

6
0 1 2 1 3 2

Exemple de sortie 1

2

• Lorsque le niveau de la mer est supérieur ou égal à $0$ et strictement inférieur à $1$, les sections $2, 3, 4, 5, 6$ sont des terres. Comme la région $[2, 6]$ est la seule île, le nombre d'îles est $1$.
• Lorsque le niveau de la mer est supérieur ou égal à $1$ et strictement inférieur à $2$, les sections $3, 5, 6$ sont des terres. Comme la région $[3, 3]$ et la région $[5, 6]$ sont des îles, le nombre d'îles est $2$.
• Lorsque le niveau de la mer est supérieur ou égal à $2$ et strictement inférieur à $3$, seule la section $5$ est une terre. Comme la région $[5, 5]$ est la seule île, le nombre d'îles est $1$.
• Lorsque le niveau de la mer atteint $3$, il n'y a plus de terre et le nombre d'îles devient $0$.

Par conséquent, le nombre maximum d'îles est $2$, on affiche donc $2$.

Exemple d'entrée 2

6
3 2 3 0 2 0

Exemple de sortie 2

2

• Lorsque le niveau de la mer est supérieur ou égal à $0$ et strictement inférieur à $2$, les sections $1, 2, 3, 5$ sont des terres. Comme la région $[1, 3]$ et la région $[5, 5]$ sont des îles, le nombre d'îles est $2$.
• Lorsque le niveau de la mer est supérieur ou égal à $2$ et strictement inférieur à $3$, les sections $1, 3$ sont des terres. Comme la région $[1, 1]$ et la région $[3, 3]$ sont des îles, le nombre d'îles est $2$.
• Lorsque le niveau de la mer atteint $3$, il n'y a plus de terre et le nombre d'îles devient $0$.

Par conséquent, le nombre maximum d'îles est $2$, on affiche donc $2$.

Exemple d'entrée 3

10
4 1 2 1 2 3 5 4 3 2

Exemple de sortie 3

3