Problembeschreibung

Die japanische Inselkette ist ein langgestreckter Archipel. Die japanische Inselkette ist durch parallele Grenzlinien in $N$ Abschnitte unterteilt. Die Abschnitte sind von einem Ende aus der Reihe nach von $1$ bis $N$ nummeriert. Die Höhe von Abschnitt $i$ ($1 \le i \le N$) beträgt $A_i$.

Die japanische Inselkette ist vom Meer umgeben, und der Meeresspiegel ist ortsunabhängig konstant. Ein Abschnitt, dessen Höhe echt größer als der Meeresspiegel ist, wird Land genannt.

Ein zusammenhängender Teil aus Land wird Insel genannt. Genauer gesagt gilt Folgendes: Für ganze Zahlen $l$, $r$ ($1 \le l \le r \le N$) heißt der Teil der japanischen Inselkette, der aus Abschnitt $l$, Abschnitt $l+1$, $\dots$, Abschnitt $r$ besteht, Bereich $[l, r]$. Ein Bereich $[l, r]$, der die folgenden Bedingungen erfüllt, wird Insel genannt:

• Abschnitt $l$, Abschnitt $l+1$, $\dots$, Abschnitt $r$ sind alle Land.
• Falls $l > 1$ gilt, ist Abschnitt $l-1$ kein Land.
• Falls $r < N$ gilt, ist Abschnitt $r+1$ kein Land.

Aufgrund des steigenden Meeresspiegels versinkt die japanische Inselkette nach und nach. Der aktuelle Meeresspiegel beträgt $0$, steigt aber mit der Zeit allmählich an, bis schließlich ganz Japan im Meer versunken ist.

JOI hat bemerkt, dass die Anzahl der Inseln Japans mit steigendem Meeresspiegel zu- und abnimmt. Bestimme die maximale Anzahl an Inseln im Zeitraum von jetzt bis zu dem Zeitpunkt, an dem es in Japan kein Land mehr gibt (einschließlich des jetzigen Zeitpunkts).

Einschränkungen

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

Eingabe / Ausgabe

Eingabe
Die Eingabe erfolgt über die Standardeingabe im folgenden Format:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Ausgabe
Gib in $1$ Zeile die maximale Anzahl an Inseln im Zeitraum von jetzt bis zu dem Zeitpunkt aus, an dem es in Japan kein Land mehr gibt (einschließlich jetzt).

Teilaufgaben

1. ($7$ Punkte) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ Punkte) $N \le 2000$
3. ($85$ Punkte) Keine zusätzlichen Einschränkungen.

Ein- und Ausgabebeispiele

Beispieleingabe 1

6
0 1 2 1 3 2

Beispielausgabe 1

2

• Wenn der Meeresspiegel mindestens $0$ und kleiner als $1$ ist, sind die Abschnitte $2, 3, 4, 5, 6$ Land. Da der Bereich $[2, 6]$ die einzige Insel ist, beträgt die Anzahl der Inseln $1$.
• Wenn der Meeresspiegel mindestens $1$ und kleiner als $2$ ist, sind die Abschnitte $3, 5, 6$ Land. Da der Bereich $[3, 3]$ und der Bereich $[5, 6]$ Inseln sind, beträgt die Anzahl der Inseln $2$.
• Wenn der Meeresspiegel mindestens $2$ und kleiner als $3$ ist, ist nur Abschnitt $5$ Land. Da der Bereich $[5, 5]$ die einzige Insel ist, beträgt die Anzahl der Inseln $1$.
• Wenn der Meeresspiegel $3$ erreicht, gibt es kein Land mehr, und die Anzahl der Inseln wird $0$.

Somit beträgt die maximale Anzahl an Inseln $2$, also wird $2$ ausgegeben.

Beispieleingabe 2

6
3 2 3 0 2 0

Beispielausgabe 2

2

• Wenn der Meeresspiegel mindestens $0$ und kleiner als $2$ ist, sind die Abschnitte $1, 2, 3, 5$ Land. Da der Bereich $[1, 3]$ und der Bereich $[5, 5]$ Inseln sind, beträgt die Anzahl der Inseln $2$.
• Wenn der Meeresspiegel mindestens $2$ und kleiner als $3$ ist, sind die Abschnitte $1, 3$ Land. Da der Bereich $[1, 1]$ und der Bereich $[3, 3]$ Inseln sind, beträgt die Anzahl der Inseln $2$.
• Wenn der Meeresspiegel $3$ erreicht, gibt es kein Land mehr, und die Anzahl der Inseln wird $0$.

Somit beträgt die maximale Anzahl an Inseln $2$, also wird $2$ ausgegeben.

Beispieleingabe 3

10
4 1 2 1 2 3 5 4 3 2

Beispielausgabe 3

3