Descrizione del problema

L'arcipelago giapponese è un arcipelago lungo e stretto. L'arcipelago giapponese è suddiviso in $N$ sezioni da linee di confine parallele. Le sezioni sono numerate da $1$ a $N$ in ordine a partire da un'estremità. L'altitudine della sezione $i$ ($1 \le i \le N$) è $A_i$.

L'arcipelago giapponese è circondato dal mare e il livello del mare è costante indipendentemente dal luogo. Una sezione la cui altitudine è strettamente maggiore del livello del mare è chiamata terraferma.

Una porzione contigua di terraferma è chiamata isola. Più precisamente: per interi $l$, $r$ ($1 \le l \le r \le N$), la parte dell'arcipelago giapponese costituita dalla sezione $l$, sezione $l+1$, $\dots$, sezione $r$ è chiamata regione $[l, r]$. Una regione $[l, r]$ che soddisfa le seguenti condizioni è chiamata isola:

• La sezione $l$, la sezione $l+1$, $\dots$, la sezione $r$ sono tutte terraferma.
• Se $l > 1$, allora la sezione $l-1$ non è terraferma.
• Se $r < N$, allora la sezione $r+1$ non è terraferma.

A causa dell'innalzamento del livello del mare, l'arcipelago giapponese sta affondando poco a poco. Il livello attuale del mare è $0$, ma sale gradualmente col passare del tempo finché l'intero Giappone diventa mare.

JOI ha notato che, man mano che il livello del mare sale, il numero di isole del Giappone aumenta e diminuisce. Trova il numero massimo di isole nel periodo che va dal presente fino al momento in cui in Giappone non rimane più terraferma (incluso il presente).

Vincoli

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

Input / Output

Input
L'input è fornito dallo standard input nel seguente formato:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Output
Stampa su $1$ riga il numero massimo di isole nel periodo che va dal presente fino al momento in cui in Giappone non rimane più terraferma (incluso il presente).

Sottoproblemi

1. ($7$ punti) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ punti) $N \le 2000$
3. ($85$ punti) Nessun vincolo aggiuntivo.

Esempi di input / output

Input di esempio 1

6
0 1 2 1 3 2

Output di esempio 1

2

• Quando il livello del mare è almeno $0$ e minore di $1$, le sezioni $2, 3, 4, 5, 6$ sono terraferma. Poiché la regione $[2, 6]$ è l'unica isola, il numero di isole è $1$.
• Quando il livello del mare è almeno $1$ e minore di $2$, le sezioni $3, 5, 6$ sono terraferma. Poiché la regione $[3, 3]$ e la regione $[5, 6]$ sono isole, il numero di isole è $2$.
• Quando il livello del mare è almeno $2$ e minore di $3$, solo la sezione $5$ è terraferma. Poiché la regione $[5, 5]$ è l'unica isola, il numero di isole è $1$.
• Quando il livello del mare raggiunge $3$, non rimane più terraferma e il numero di isole diventa $0$.

Pertanto il numero massimo di isole è $2$, quindi stampa $2$.

Input di esempio 2

6
3 2 3 0 2 0

Output di esempio 2

2

• Quando il livello del mare è almeno $0$ e minore di $2$, le sezioni $1, 2, 3, 5$ sono terraferma. Poiché la regione $[1, 3]$ e la regione $[5, 5]$ sono isole, il numero di isole è $2$.
• Quando il livello del mare è almeno $2$ e minore di $3$, le sezioni $1, 3$ sono terraferma. Poiché la regione $[1, 1]$ e la regione $[3, 3]$ sono isole, il numero di isole è $2$.
• Quando il livello del mare raggiunge $3$, non rimane più terraferma e il numero di isole diventa $0$.

Pertanto il numero massimo di isole è $2$, quindi stampa $2$.

Input di esempio 3

10
4 1 2 1 2 3 5 4 3 2

Output di esempio 3

3