← 返回题目列表

AtCoder · joi2019_yo_d

D. 日本沉没

中文机器翻译题面 查看原题

配点: 100 点

問題文

日本列岛是一个狭长的群岛。日本列岛被平行的边界划分。 它分为 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