Islands

Whenever it rains, Farmer John's field floods. Because the field is not perfectly level, the water rises unevenly, and the exposed land breaks up into a number of disjoint "islands".

The field is a one-dimensional landscape given by $N$ consecutive height values $H_1, H_2, \dots, H_N$. Assume the field is bounded on both ends by walls of effectively infinite height. As a rainstorm fills the field, the lowest regions are covered first, creating a number of separate islands, and eventually everything is submerged. The instant the water level becomes equal to the height of a piece of land, that piece of land is considered underwater.

For example, with the heights $3, 5, 2, 3, 1, 4, 2, 3$, adding just over $1$ unit of water leaves $4$ islands (the most that ever appear at once); after a total of $7$ units of water only $2$ islands remain exposed.

Compute the maximum number of islands that are ever visible at a single point in time, as the water rises from empty until the entire field is underwater.

• The first line contains the integer $N$ ($1 \le N \le 100{,}000$).
• Each of the next $N$ lines contains one height $H_i$ ($1 \le H_i \le 1{,}000{,}000{,}000$).

• Print a single integer: the maximum number of islands that appear at any single moment during the storm.

Consider the heights $3, 5, 2, 3, 1, 4, 2, 3$. When the water level lies strictly between $2$ and $3$, only the cells of height $3$ or more remain above water, splitting the land into $4$ separate islands — the maximum seen at any single instant.