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 翻译