← 返回题目列表

AtCoder · awc0008_b

B. 从海上可见的建筑物

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

分数: 233 分

问题陈述

高桥正在参观沿海的一个小镇。

有 N 建筑物从海上向陆地呈直线排列。建筑物都有编号 1, 2, \ldots, N 按离海最近的顺序,是哪栋楼 1 离海和建筑最近 N 离海最远。建筑物高度 i is H_i。所有建筑物的宽度相同,并排成一条直线,彼此之间没有间隙。

高桥正从海上足够远的地方正面观察这排建筑。不受前方建筑物遮挡而能够看到的建筑物称为“从海上可见”的建筑物,定义如下:

  • 大楼 从海上始终可以看到 1 。
  • 对于 i \geq 2,让 M 是建筑物中的最大高度 1, 2, \ldots, i-1。如果 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
  • 第一行给出建筑物的数量 N.
  • 第二行给出每栋建筑物的高度 H_1, H_2, \ldots, H_N,用空格分隔。

输出

在一行中打印从海上可见的建筑物数量。


示例输入 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