Opis problemu

Archipelag Japoński jest długim i wąskim archipelagiem. Archipelag Japoński jest podzielony równoległymi liniami granicznymi na $N$ odcinków. Odcinki są ponumerowane kolejno od $1$ do $N$, zaczynając od jednego z końców. Wysokość odcinka $i$ ($1 \le i \le N$) wynosi $A_i$.

Archipelag Japoński jest otoczony morzem, a poziom morza jest stały niezależnie od miejsca. Odcinek, którego wysokość jest ściśle większa od poziomu morza, nazywamy lądem.

Spójny fragment lądu nazywamy wyspą. Dokładniej rzecz ujmując: dla liczb całkowitych $l$, $r$ ($1 \le l \le r \le N$) część Archipelagu Japońskiego składającą się z odcinka $l$, odcinka $l+1$, $\dots$, odcinka $r$ nazywamy obszarem $[l, r]$. Obszar $[l, r]$ spełniający poniższe warunki nazywamy wyspą:

• Odcinek $l$, odcinek $l+1$, $\dots$, odcinek $r$ są wszystkie lądem.
• Jeśli $l > 1$, to odcinek $l-1$ nie jest lądem.
• Jeśli $r < N$, to odcinek $r+1$ nie jest lądem.

Wskutek podnoszenia się poziomu morza Archipelag Japoński powoli tonie. Obecnie poziom morza wynosi $0$, ale z upływem czasu stopniowo się podnosi, aż w końcu cała Japonia stanie się morzem.

JOI zauważył, że wraz ze wzrostem poziomu morza liczba wysp w Japonii rośnie i maleje. Wyznacz maksymalną liczbę wysp w okresie od chwili obecnej aż do momentu, gdy w Japonii nie będzie już żadnego lądu (wliczając chwilę obecną).

Ograniczenia

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

Wejście / Wyjście

Wejście
Wejście podawane jest ze standardowego wejścia w następującym formacie:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Wyjście
Wypisz w $1$ wierszu maksymalną liczbę wysp w okresie od chwili obecnej do momentu, gdy w Japonii nie będzie już lądu (wliczając chwilę obecną).

Podzadania

1. ($7$ punktów) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ punktów) $N \le 2000$
3. ($85$ punktów) Brak dodatkowych ograniczeń.

Przykłady wejścia / wyjścia

Przykładowe wejście 1

6
0 1 2 1 3 2

Przykładowe wyjście 1

2

• Gdy poziom morza wynosi co najmniej $0$ i mniej niż $1$, lądem są odcinki $2, 3, 4, 5, 6$. Ponieważ obszar $[2, 6]$ jest jedyną wyspą, liczba wysp wynosi $1$.
• Gdy poziom morza wynosi co najmniej $1$ i mniej niż $2$, lądem są odcinki $3, 5, 6$. Ponieważ obszar $[3, 3]$ oraz obszar $[5, 6]$ są wyspami, liczba wysp wynosi $2$.
• Gdy poziom morza wynosi co najmniej $2$ i mniej niż $3$, lądem jest tylko odcinek $5$. Ponieważ obszar $[5, 5]$ jest jedyną wyspą, liczba wysp wynosi $1$.
• Gdy poziom morza osiągnie $3$, nie ma już lądu, a liczba wysp wynosi $0$.

Zatem maksymalna liczba wysp wynosi $2$, więc należy wypisać $2$.

Przykładowe wejście 2

6
3 2 3 0 2 0

Przykładowe wyjście 2

2

• Gdy poziom morza wynosi co najmniej $0$ i mniej niż $2$, lądem są odcinki $1, 2, 3, 5$. Ponieważ obszar $[1, 3]$ oraz obszar $[5, 5]$ są wyspami, liczba wysp wynosi $2$.
• Gdy poziom morza wynosi co najmniej $2$ i mniej niż $3$, lądem są odcinki $1, 3$. Ponieważ obszar $[1, 1]$ oraz obszar $[3, 3]$ są wyspami, liczba wysp wynosi $2$.
• Gdy poziom morza osiągnie $3$, nie ma już lądu, a liczba wysp wynosi $0$.

Zatem maksymalna liczba wysp wynosi $2$, więc należy wypisać $2$.

Przykładowe wejście 3

10
4 1 2 1 2 3 5 4 3 2

Przykładowe wyjście 3

3