Japan Sinks

Interview

Time limit2sMemory limit512 MB

Summary

Raise the sea level through the section heights and track how maximal runs of above-level sections merge; report the largest island count seen.

Level: Medium5 of 10
Topics: Sorting, Union-find, Simulation, Array
Solved: No attempts yet

Problem

The Japanese archipelago is a long, narrow chain of islands. It is divided into N sections by parallel boundary lines. The sections are numbered 1 to N from one end. The height of section i (1 ≤ i ≤ N) is A_i.

The archipelago is surrounded by the sea, and the sea level is constant everywhere. A section whose height is greater than the sea level is called land.

A maximal contiguous stretch of land is called an island. More precisely, for integers l, r (1 ≤ l ≤ r ≤ N), the part of the 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, section l-1 is not land.
If r < N, section r+1 is not land.

Because the sea level is rising, the archipelago is gradually sinking. The current sea level is 0, but it 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 goes up and down. He wants to find the maximum number of islands over the period from now until Japan has no land left (including now).

Input

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

N
A_1 A_2 ... A_N

Output

Print the maximum number of islands over the period from now until Japan has no land left (including now) on one line.

Constraints

1 ≤ N ≤ 100000 (= 10^5)
0 ≤ A_i ≤ 1000000000 (= 10^9) (1 ≤ i ≤ N)

Examples3

Example 1
Input
```
6
0 1 2 1 3 2
```
Expected output
```
2
```
Example 2
Input
```
6
3 2 3 0 2 0
```
Expected output
```
2
```
Example 3
Input
```
10
4 1 2 1 2 3 5 4 3 2
```
Expected output
```
3
```