AT_joi2019_yo_d.日本沈没 (Japan Sinks)

日本列岛是一条细长的列岛。日本列岛被平行的边界线分成了 $N$ 个区块。每个区块从一端开始依次编号为 $1$ 到 $N$。第 $i$ 个区块（$1 \leq i \leq N$）的高度为 $A_i$。

日本列岛被海洋包围，海平面高度在所有地方都是一样的。高度高于海平面的区块被称为陆地。

陆地连续的部分被称为岛屿。更准确地说，定义如下：对于整数 $l$、$r$（$1 \leq l \leq r \leq N$），由区块 $l$、$l+1$、...、$r$ 组成的部分称为区间 [$l, r$]。满足以下条件的区间 [$l, r$] 被称为岛屿：

• 区块 $l$、$l+1$、...、$r$ 都是陆地。
• 如果 $l > 1$，则区块 $l-1$ 不是陆地。
• 如果 $r < N$，则区块 $r+1$ 不是陆地。

由于海平面上升，日本列岛正在逐渐下沉。当前海平面高度为 $0$，但随着时间推移会逐渐升高，最终整个日本都会被海水淹没。

JOI 君注意到，随着海平面高度的上升，日本的岛屿数量会发生变化。请你求出，从现在到日本没有任何陆地为止（包括现在），岛屿数量的最大值。

输入以以下格式从标准输入读入。

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

请输出从现在到日本没有任何陆地为止（包括现在）期间，岛屿数量的最大值。

限制条件

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

子任务

1.（7 分）$N \leq 2000$，$A_i \leq 2000$（$1 \leq i \leq N$）
2.（8 分）$N \leq 2000$
3.（85 分）无额外限制。

样例解释 1

• 当海平面高度在 $0$ 以上 $1$ 未满时，区块 $2, 3, 4, 5, 6$ 是陆地。区间 [$2, 6$] 是唯一的岛屿，因此岛屿数量为 $1$。
• 当海平面高度在 $1$ 以上 $2$ 未满时，区块 $3, 5, 6$ 是陆地。区间 [$3, 3$] 和区间 [$5, 6$] 是岛屿，因此岛屿数量为 $2$。
• 当海平面高度在 $2$ 以上 $3$ 未满时，只有区块 $5$ 是陆地。区间 [$5, 5$] 是唯一的岛屿，因此岛屿数量为 $1$。
• 当海平面高度达到 $3$ 时，所有陆地都消失，岛屿数量为 $0$。

因此岛屿数量的最大值为 $2$，输出 $2$。

样例解释 2

• 当海平面高度在 $0$ 以上 $2$ 未满时，区块 $1, 2, 3, 5$ 是陆地。区间 [$1, 3$] 和区间 [$5, 5$] 是岛屿，因此岛屿数量为 $2$。
• 当海平面高度在 $2$ 以上 $3$ 未满时，区块 $1, 3$ 是陆地。区间 [$1, 1$] 和区间 [$3, 3$] 是岛屿，因此岛屿数量为 $2$。
• 当海平面高度达到 $3$ 时，所有陆地都消失，岛屿数量为 $0$。

因此岛屿数量的最大值为 $2$，输出 $2$。

由 ChatGPT 4.1 翻译