Descripción del problema

El archipiélago japonés es un archipiélago largo y estrecho. El archipiélago japonés está dividido en $N$ secciones mediante líneas divisorias paralelas. Las secciones están numeradas del $1$ al $N$ en orden desde un extremo. La altitud de la sección $i$ ($1 \le i \le N$) es $A_i$.

El archipiélago japonés está rodeado por el mar, y el nivel del mar es constante independientemente del lugar. Una sección cuya altitud es estrictamente mayor que el nivel del mar se denomina tierra firme.

Una porción continua de tierra firme se denomina isla. Más precisamente, para enteros $l$, $r$ ($1 \le l \le r \le N$), la parte del archipiélago japonés formada por la sección $l$, la sección $l+1$, $\dots$, la sección $r$ se denomina región $[l, r]$. Una región $[l, r]$ que cumple las siguientes condiciones se denomina isla:

• La sección $l$, la sección $l+1$, $\dots$, la sección $r$ son todas tierra firme.
• Si $l > 1$, entonces la sección $l-1$ no es tierra firme.
• Si $r < N$, entonces la sección $r+1$ no es tierra firme.

Debido al aumento del nivel del mar, el archipiélago japonés se está hundiendo poco a poco. El nivel del mar actual es $0$, pero sube gradualmente con el paso del tiempo hasta que finalmente todo Japón se convierte en mar.

JOI notó que, a medida que sube el nivel del mar, el número de islas de Japón aumenta y disminuye. Encuentra el número máximo de islas durante el período desde el presente hasta que no quede tierra firme en Japón (incluyendo el presente).

Restricciones

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

Entrada / Salida

Entrada
La entrada se proporciona desde la entrada estándar en el siguiente formato:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Salida
Imprime en $1$ línea el número máximo de islas durante el período desde el presente hasta que no quede tierra firme en Japón (incluyendo el presente).

Subtareas

1. ($7$ puntos) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ puntos) $N \le 2000$
3. ($85$ puntos) Sin restricciones adicionales.

Ejemplo de entrada / salida

Entrada de ejemplo 1

6
0 1 2 1 3 2

Salida de ejemplo 1

2

• Cuando el nivel del mar es al menos $0$ y menor que $1$, las secciones $2, 3, 4, 5, 6$ son tierra firme. Como la región $[2, 6]$ es la única isla, el número de islas es $1$.
• Cuando el nivel del mar es al menos $1$ y menor que $2$, las secciones $3, 5, 6$ son tierra firme. Como la región $[3, 3]$ y la región $[5, 6]$ son islas, el número de islas es $2$.
• Cuando el nivel del mar es al menos $2$ y menor que $3$, solo la sección $5$ es tierra firme. Como la región $[5, 5]$ es la única isla, el número de islas es $1$.
• Cuando el nivel del mar alcanza $3$, ya no queda tierra firme y el número de islas pasa a ser $0$.

Por lo tanto, el número máximo de islas es $2$, así que se imprime $2$.

Entrada de ejemplo 2

6
3 2 3 0 2 0

Salida de ejemplo 2

2

• Cuando el nivel del mar es al menos $0$ y menor que $2$, las secciones $1, 2, 3, 5$ son tierra firme. Como la región $[1, 3]$ y la región $[5, 5]$ son islas, el número de islas es $2$.
• Cuando el nivel del mar es al menos $2$ y menor que $3$, las secciones $1, 3$ son tierra firme. Como la región $[1, 1]$ y la región $[3, 3]$ son islas, el número de islas es $2$.
• Cuando el nivel del mar alcanza $3$, ya no queda tierra firme y el número de islas pasa a ser $0$.

Por lo tanto, el número máximo de islas es $2$, así que se imprime $2$.

Entrada de ejemplo 3

10
4 1 2 1 2 3 5 4 3 2

Salida de ejemplo 3

3