Problem Description

The Japanese archipelago is a long, narrow island chain. It is divided into $ N $ sections by parallel boundaries. The sections are numbered from $ 1 $ to $ N $ in order from one end. The height of section $ i $ ($1 \leq i \leq N$) is $ A_i $.

The Japanese archipelago is surrounded by the sea, and the sea level is constant everywhere. A section is called land if its height is higher than the sea level.

A contiguous part of land is called an island. More precisely, for integers $ l $ and $ r $ ($1 \leq l \leq r \leq N$), the part of the Japanese archipelago consisting of sections $ l $, $ l+1 $, ..., $ r $ is called the region \[$ l, r $\]. A region \[$ l, r $\] is called an island if it satisfies the following conditions:

• Sections $ l $, $ l+1 $, ..., $ 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 gradually sinking. The current sea level is $ 0 $, but it will gradually rise until the entire archipelago is submerged.

JOI noticed that the number of islands in Japan will increase and decrease as the sea level rises. He wants to find the maximum number of islands from now until there is no land left in Japan (including the present).

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

Output Format

Output the maximum number of islands from now until there is no land left in Japan (including the present) in one line.

Sample Input and Output

Sample Input #1

6
0 1 2 1 3 2

Sample Output #1

2

Sample Input #2

6
3 2 3 0 2 0

Sample Output #2

2

Sample Input #3

10
4 1 2 1 2 3 5 4 3 2

Sample Output #3

3

Notes/Hints

Constraints

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

Subtasks

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

Sample Explanation 1

• When the sea level is between $ 0 $ and less than $ 1 $, sections $ 2, 3, 4, 5, 6 $ are land. The region [$ 2, 6 $] is the only island, so the number of islands is $ 1 $.
• When the sea level is between $ 1 $ and less than $ 2 $, sections $ 3, 5, 6 $ are land. The regions [$ 3, 3 $] and [$ 5, 6 $] are islands, so the number of islands is $ 2 $.
• When the sea level is between $ 2 $ and less than $ 3 $, only section $ 5 $ is land. The region [$ 5, 5 $] is the only island, so the number of islands is $ 1 $.
• When the sea level reaches $ 3 $, there is no land, and the number of islands is $ 0 $.

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

Sample Explanation 2

• When the sea level is between $ 0 $ and less than $ 2 $, sections $ 1, 2, 3, 5 $ are land. The regions [$ 1, 3 $] and [$ 5, 5 $] are islands, so the number of islands is $ 2 $.
• When the sea level is between $ 2 $ and less than $ 3 $, sections $ 1, 3 $ are land. The regions [$ 1, 1 $] and [$ 3, 3 $] are islands, so the number of islands is $ 2 $.
• When the sea level reaches $ 3 $, there is no land, and the number of islands is $ 0 $.

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

见题面 Input 部分

见题面 Output 部分