2637: Islands[USACO-2012-USOpen-B]
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0
[Status] [Submit] [Creator:]
Description
每次下雨，FJ的农场都会被淹。然而，由于地面不平，下雨后农场上会留下由大片的水分开的一个个“岛屿”。
可以把FJ的农场看作是由N个连续高度值H(1)...H(N)组成的一个一维景观。假设这个景观周围都是无限高的栅栏，那么在暴雨期间，地势最低的区域先被水覆盖，然后会产生出一些"岛屿"，随着水位的不断上升，水位的高度会在一瞬间与“岛屿”的高度相等，此时认为这个“岛屿”被淹了，最终农场会全部被淹没在水下面。
举个例子，如上图所示，左边的图中，如果我们加入刚超过1单位的水时，那么会产生4个“岛屿”（4个也是在整个过程中我们能够看到岛屿数量的最大值），然后继续倒水，当我们总共加入的水达到7个单位时，如右图所示，只露出了2个“岛屿”，最终会全部淹没在水下面。
请计算出，在整个期间，我们可能会看到的“岛屿”数量的最大值。
可以把FJ的农场看作是由N个连续高度值H(1)...H(N)组成的一个一维景观。假设这个景观周围都是无限高的栅栏，那么在暴雨期间，地势最低的区域先被水覆盖，然后会产生出一些"岛屿"，随着水位的不断上升，水位的高度会在一瞬间与“岛屿”的高度相等，此时认为这个“岛屿”被淹了，最终农场会全部被淹没在水下面。
举个例子，如上图所示，左边的图中，如果我们加入刚超过1单位的水时，那么会产生4个“岛屿”（4个也是在整个过程中我们能够看到岛屿数量的最大值），然后继续倒水，当我们总共加入的水达到7个单位时，如右图所示，只露出了2个“岛屿”，最终会全部淹没在水下面。
请计算出，在整个期间，我们可能会看到的“岛屿”数量的最大值。
Input
第一行，一个整数N，表示将会给出的高度值的数量
接下来N行，每行一个整数，表示高度值H(i),1≤H(i)≤1000000000
接下来N行，每行一个整数，表示高度值H(i),1≤H(i)≤1000000000
Output
一行，一个整数，表示随着水位的不断上升，在整个过程中，我们可能会看到的“岛屿”数量的最大值
Sample Input Copy
8
3
5
2
3
1
4
2
3
Sample Output Copy
4