Tehtävänanto

Japanin saaristo on pitkä ja kapea saaristo. Japanin saaristo on jaettu yhdensuuntaisilla rajaviivoilla $N$ lohkoon. Lohkot on numeroitu toisesta päästä alkaen järjestyksessä $1$ – $N$. Lohkon $i$ ($1 \le i \le N$) korkeus on $A_i$.

Japanin saaristoa ympäröi meri, ja merenpinnan korkeus on vakio paikasta riippumatta. Lohkoa, jonka korkeus on aidosti suurempi kuin merenpinnan korkeus, kutsutaan maaksi.

Yhtenäistä maan osaa kutsutaan saareksi. Täsmällisemmin sanottuna: kokonaisluvuilla $l$, $r$ ($1 \le l \le r \le N$) Japanin saariston osaa, joka koostuu lohkosta $l$, lohkosta $l+1$, $\dots$, lohkosta $r$, kutsutaan alueeksi $[l, r]$. Seuraavat ehdot täyttävää aluetta $[l, r]$ kutsutaan saareksi:

• Lohko $l$, lohko $l+1$, $\dots$, lohko $r$ ovat kaikki maata.
• Jos $l > 1$, niin lohko $l-1$ ei ole maata.
• Jos $r < N$, niin lohko $r+1$ ei ole maata.

Merenpinnan nousun vuoksi Japanin saaristo uppoaa vähitellen. Nykyinen merenpinnan korkeus on $0$, mutta ajan myötä se nousee vähitellen, kunnes lopulta koko Japani muuttuu mereksi.

JOI huomasi, että merenpinnan noustessa Japanin saarten lukumäärä kasvaa ja vähenee. Selvitä saarten lukumäärän suurin arvo ajanjaksolla nykyhetkestä siihen asti, kunnes Japanissa ei ole enää lainkaan maata (nykyhetki mukaan lukien).

Rajoitukset

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

Syöte ja tuloste

Syöte
Syöte annetaan vakiosyötteestä seuraavassa muodossa:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Tuloste
Tulosta $1$ riville saarten lukumäärän suurin arvo ajanjaksolla nykyhetkestä siihen asti, kunnes Japanissa ei ole enää maata (nykyhetki mukaan lukien).

Osatehtävät

1. ($7$ pistettä) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ pistettä) $N \le 2000$
3. ($85$ pistettä) Ei lisärajoituksia.

Esimerkkisyötteet ja -tulosteet

Esimerkkisyöte 1

6
0 1 2 1 3 2

Esimerkkituloste 1

2

• Kun merenpinnan korkeus on vähintään $0$ ja alle $1$, lohkot $2, 3, 4, 5, 6$ ovat maata. Koska alue $[2, 6]$ on ainoa saari, saarten lukumäärä on $1$.
• Kun merenpinnan korkeus on vähintään $1$ ja alle $2$, lohkot $3, 5, 6$ ovat maata. Koska alue $[3, 3]$ ja alue $[5, 6]$ ovat saaria, saarten lukumäärä on $2$.
• Kun merenpinnan korkeus on vähintään $2$ ja alle $3$, vain lohko $5$ on maata. Koska alue $[5, 5]$ on ainoa saari, saarten lukumäärä on $1$.
• Kun merenpinnan korkeus saavuttaa arvon $3$, maata ei ole enää jäljellä ja saarten lukumääräksi tulee $0$.

Näin ollen saarten suurin lukumäärä on $2$, joten tulostetaan $2$.

Esimerkkisyöte 2

6
3 2 3 0 2 0

Esimerkkituloste 2

2

• Kun merenpinnan korkeus on vähintään $0$ ja alle $2$, lohkot $1, 2, 3, 5$ ovat maata. Koska alue $[1, 3]$ ja alue $[5, 5]$ ovat saaria, saarten lukumäärä on $2$.
• Kun merenpinnan korkeus on vähintään $2$ ja alle $3$, lohkot $1, 3$ ovat maata. Koska alue $[1, 1]$ ja alue $[3, 3]$ ovat saaria, saarten lukumäärä on $2$.
• Kun merenpinnan korkeus saavuttaa arvon $3$, maata ei ole enää jäljellä ja saarten lukumääräksi tulee $0$.

Näin ollen saarten suurin lukumäärä on $2$, joten tulostetaan $2$.

Esimerkkisyöte 3

10
4 1 2 1 2 3 5 4 3 2

Esimerkkituloste 3

3