C - Skyline View Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

東西に伸びる一本の通りに沿って、N 棟のビルが一列に並んでいます。西から順にビル 1、ビル 2、…、ビル N と番号がついており、ビル i の高さは H_i です。

高橋君は、ビル 1 よりもさらに西側の地点に立って、東の方向を眺めています。ビルが見えるかどうかは、高さのみによって次のように決まります：

  • ビル i より西側にあるすべてのビル（ビル 1 からビル i-1 まで）の高さがいずれも H_i 未満である場合、ビル i は高橋君から見えます。
  • そうでない場合、すなわち、ビル 1 からビル i-1 までの中に高さが H_i 以上のビルが1つでも存在する場合、ビル i は手前のビルに遮られて見えません。高さがちょうど同じビルが手前にある場合も遮られることに注意してください。

特に、ビル 1 は西側にビルが存在しないため、常に見えます。

高橋君は、N 棟のビルの中からちょうど1棟を選んで取り壊します。取り壊すビルは、見えているビル・見えていないビルのいずれでも構いませんが、この操作は必ず1回行わなければならず、省略することはできません。取り壊されたビルは完全に消滅し、残ったビルの並び順はそのままで、取り壊されたビルが存在しないものとして改めて眺望を判定します。すなわち、取り壊されたビルは他のビルを遮ることもなくなり、見えるビルの数にもカウントしません。

高橋君は、取り壊すビルを最適に選ぶことで、取り壊し後に見えるビルの数を最大化したいと考えています。

最適にビルを1棟選んで取り壊したとき、高橋君から見えるビルの数の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq H_i \leq 10^9
  • 入力はすべて整数である。

入力

N
H_1 H_2 \cdots H_N
  • 1 行目には、ビルの棟数を表す整数 N が与えられる。
  • 2 行目には、各ビルの高さを表す整数 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。

出力

最適なビルを1棟取り壊したときに、高橋君から見えるビルの数の最大値を 1 行で出力せよ。

入力例 1

5
2 1 3 2 4

出力例 1

3

入力例 2

6
5 3 5 6 6 7

出力例 2

4

入力例 3

12
4 2 6 3 5 7 1 7 8 2 9 6

出力例 3

5

入力例 4

30
100 20 50 120 110 130 10 125 140 140 60 150 149 151 5 152 80 153 153 154 1 90 155 154 156 2 157 50 158 159

出力例 4

15

入力例 5

1
1000000000

出力例 5

0

Score : 366 pts

Problem Statement

Along a straight road running east-west, N buildings stand in a row. They are numbered Building 1, Building 2, …, Building N from west to east, and the height of Building i is H_i.

Takahashi is standing at a point further west than Building 1, looking toward the east. Whether a building is visible or not is determined solely by height as follows:

  • If the heights of all buildings to the west of Building i (from Building 1 to Building i-1) are strictly less than H_i, then Building i is visible to Takahashi.
  • Otherwise, that is, if there exists at least one building among Building 1 to Building i-1 whose height is greater than or equal to H_i, then Building i is blocked by a building in front and is not visible. Note that a building with exactly the same height in front also blocks it.

In particular, Building 1 is always visible since there are no buildings to its west.

Takahashi will choose exactly one building from the N buildings and demolish it. The building to demolish may be either a visible or non-visible building, but this operation must be performed exactly once and cannot be skipped. The demolished building completely disappears, and the view is re-evaluated with the remaining buildings in their original order, treating the demolished building as if it never existed. That is, the demolished building no longer blocks any other buildings, and it is not counted in the number of visible buildings.

Takahashi wants to maximize the number of visible buildings after the demolition by optimally choosing which building to demolish.

Find the maximum number of buildings visible to Takahashi when one building is optimally chosen and demolished.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq H_i \leq 10^9
  • All inputs are integers.

Input

N
H_1 H_2 \cdots H_N
  • The first line contains an integer N representing the number of buildings.
  • The second line contains integers H_1, H_2, \ldots, H_N separated by spaces, representing the height of each building.

Output

Print in one line the maximum number of buildings visible to Takahashi when one building is optimally chosen and demolished.

Sample Input 1

5
2 1 3 2 4

Sample Output 1

3

Sample Input 2

6
5 3 5 6 6 7

Sample Output 2

4

Sample Input 3

12
4 2 6 3 5 7 1 7 8 2 9 6

Sample Output 3

5

Sample Input 4

30
100 20 50 120 110 130 10 125 140 140 60 150 149 151 5 152 80 153 153 154 1 90 155 154 156 2 157 50 158 159

Sample Output 4

15

Sample Input 5

1
1000000000

Sample Output 5

0