B - 海から見える建物 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君は海沿いの街を訪れています。

海から陸に向かって一直線に、N 棟の建物が並んでいます。建物には海に近い方から順に 1, 2, \ldots, N と番号が付けられており、建物 1 が最も海に近く、建物 N が最も海から遠くにあります。建物 i の高さは H_i です。すべての建物の幅は同じで、隙間なく一直線上に並んでいます。

高橋君は海上の十分に遠い地点からこの建物の列を正面に眺めています。手前の建物に遮られずに見える建物を「海から見える」建物と呼ぶことにし、次のように定めます。

  • 建物 1 は常に海から見えます。
  • i \geq 2 のとき、建物 1, 2, \ldots, i-1 の高さの最大値を M とします。H_i > M であれば建物 i は海から見えます。H_i \leq M であれば建物 i は海から見えません。

すなわち、建物 i が海から見えるのは、それより手前（海側）にあるすべての建物よりも厳密に高い場合に限ります。

海から見える建物の個数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N
H_1 H_2 \ldots H_N
  • 1 行目には、建物の棟数 N が与えられる。
  • 2 行目には、各建物の高さ H_1, H_2, \ldots, H_N がスペース区切りで与えられる。

出力

海から見える建物の個数を 1 行で出力せよ。

入力例 1

5
3 1 4 1 5

出力例 1

3

入力例 2

8
10 5 15 8 15 20 12 25

出力例 2

4

入力例 3

12
100 50 80 120 90 110 150 140 200 180 250 300

出力例 3

6

Score : 233 pts

Problem Statement

Takahashi is visiting a town along the coast.

There are N buildings lined up in a straight line from the sea toward the land. The buildings are numbered 1, 2, \ldots, N in order from the closest to the sea, where building 1 is closest to the sea and building N is farthest from the sea. The height of building i is H_i. All buildings have the same width and are lined up in a straight line with no gaps between them.

Takahashi is viewing this row of buildings head-on from a sufficiently distant point on the sea. A building that can be seen without being blocked by buildings in front of it is called a building "visible from the sea," defined as follows:

  • Building 1 is always visible from the sea.
  • For i \geq 2, let M be the maximum height among buildings 1, 2, \ldots, i-1. If H_i > M, then building i is visible from the sea. If H_i \leq M, then building i is not visible from the sea.

In other words, building i is visible from the sea if and only if it is strictly taller than all buildings in front of it (on the sea side).

Find the number of buildings visible from the sea.

Constraints

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

Input

N
H_1 H_2 \ldots H_N
  • The first line gives the number of buildings N.
  • The second line gives the heights of each building H_1, H_2, \ldots, H_N, separated by spaces.

Output

Print the number of buildings visible from the sea in one line.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

3

Sample Input 2

8
10 5 15 8 15 20 12 25

Sample Output 2

4

Sample Input 3

12
100 50 80 120 90 110 150 140 200 180 250 300

Sample Output 3

6