问题文

日本列岛是一个细长的列岛。日本列岛被平行的边界线分割为 $N$ 个区块。每个区块从一端到另一端都被编号为 $1$ 到 $N$。区块 $i$ ($1 ≤ i ≤ N$) 的高度是 $A_i$。

日本列岛被海洋环绕，海平面的高度不受位置的影响而保持不变。高于海平面的区块被称为陆地。

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

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

随着海平面的上升，日本列岛逐渐沉没。当前的海平面高度为 $0$，但随着时间的推移，海平面会逐渐上升，最终整个日本将变成海洋。

JOI 君注意到，海平面上升时，日本的岛屿数量会增加或减少。现在，他想求出从当前开始直到日本没有陆地为止（包括当前），岛屿数量的最大值。

制约

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

输入

输入以以下格式从标准输入中给出。

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

输出

输出岛屿数量的最大值，即从当前开始直到日本没有陆地为止（包括当前）的岛屿数量，以一行输出。

小任务

1. ($7$ 分) $N ≤ 2000$，$A_i ≤ 2000$ ($1 ≤ i ≤ N$)
2. ($8$ 分) $N ≤ 2000$
3. ($85$ 分) 没有额外的限制。

输入例 1

6
0 1 2 1 3 2

输出例 1

2

• 当海平面高度为 $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

6
3 2 3 0 2 0

输出例 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$。

输入例 3

10
4 1 2 1 2 3 5 4 3 2

输出例 3

3