分数: 233 分
问题陈述
高桥喜欢爬山,他正在勘测某座山脉的地形。
这座山脉有 N 点排列成一条线,以及每个点的高程 i (1 \leq i \leq N) 是 R_i。高桥想要计算在这个海拔序列中存在多少个“之字形”部分。
“之字形”定义如下。连续三分 i, i+1, i+2 (1 \leq i \leq N - 2),从点开始的三元组 如果 i 满足以下任一条件,则称为“之字形”:
- R_i < R_{i+1} 和 R_{i+1} > R_{i+2} (海拔先升高后降低的模式)
- R_i > R_{i+1} 和 R_{i+1} < R_{i+2} (海拔先下降然后上升的模式)
换句话说,当中间点的标高高于两个相邻点(峰型)或低于两个相邻点(谷型)时,就会出现锯齿形。如果相邻点具有相同的高程,则这两个条件都不满足,因此不算作锯齿形。
求锯齿形三元组的总数,即 i (1 \leq i \leq N - 2) 满足上述条件。
约束
- 3 \leq N \leq 2 \times 10^5
- 1 \leq R_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数。
输入
N R_1 R_2 \ldots R_N
- 第一行包含一个整数 N 代表点数。
- 第二行包含整数 R_1, R_2, \ldots, R_N 代表每个点的高程,以空格分隔。
输出
输出单行中之字形三元组的总数。
示例输入 1
5 1 3 2 4 1
示例输出 1
3
示例输入 2
8 1 2 3 4 5 6 7 8
示例输出 2
0
示例输入 3
10 10 5 8 3 7 2 9 1 6 4
示例输出 3
8