分数: 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