Problem Description

The Japanese archipelago is a long and narrow archipelago. The Japanese archipelago is divided into $N$ sections by parallel boundary lines. The sections are numbered from $1$ to $N$ in order from one end. The altitude of section $i$ ($1 \le i \le N$) is $A_i$.

The Japanese archipelago is surrounded by the sea, and the sea level is constant regardless of location. A section whose altitude is strictly greater than the sea level is called land.

A contiguous portion of land is called an island. More precisely, it is as follows. For integers $l$, $r$ ($1 \le l \le r \le N$), the portion of the Japanese archipelago consisting of section $l$, section $l+1$, $\dots$, section $r$ is called region $[l, r]$. A region $[l, r]$ satisfying the following conditions is called an island:

• Section $l$, section $l+1$, $\dots$, section $r$ are all land.
• If $l > 1$, then section $l-1$ is not land.
• If $r < N$, then section $r+1$ is not land.

Due to rising sea levels, the Japanese archipelago is sinking little by little. The current sea level is $0$, but it gradually rises over time, and eventually the whole of Japan becomes sea.

JOI noticed that as the sea level rises, the number of islands in Japan increases and decreases. Find the maximum number of islands during the period from the present until there is no land left in Japan (including the present).

Constraints

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

Input / Output

Input
The input is given from Standard Input in the following format:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Output
Output on $1$ line the maximum number of islands during the period from the present until there is no land left in Japan (including the present).

Subtasks

1. ($7$ points) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ points) $N \le 2000$
3. ($85$ points) No additional constraints.

Sample Input / Output

Sample Input 1

6
0 1 2 1 3 2

Sample Output 1

2

• When the sea level is at least $0$ and less than $1$, sections $2, 3, 4, 5, 6$ are land. Since region $[2, 6]$ is the only island, the number of islands is $1$.
• When the sea level is at least $1$ and less than $2$, sections $3, 5, 6$ are land. Since region $[3, 3]$ and region $[5, 6]$ are islands, the number of islands is $2$.
• When the sea level is at least $2$ and less than $3$, only section $5$ is land. Since region $[5, 5]$ is the only island, the number of islands is $1$.
• When the sea level reaches $3$, there is no land left, and the number of islands becomes $0$.

Therefore, the maximum number of islands is $2$, so output $2$.

Sample Input 2

6
3 2 3 0 2 0

Sample Output 2

2

• When the sea level is at least $0$ and less than $2$, sections $1, 2, 3, 5$ are land. Since region $[1, 3]$ and region $[5, 5]$ are islands, the number of islands is $2$.
• When the sea level is at least $2$ and less than $3$, sections $1, 3$ are land. Since region $[1, 1]$ and region $[3, 3]$ are islands, the number of islands is $2$.
• When the sea level reaches $3$, there is no land left, and the number of islands becomes $0$.

Therefore, the maximum number of islands is $2$, so output $2$.

Sample Input 3

10
4 1 2 1 2 3 5 4 3 2

Sample Output 3

3