← 返回题目列表

AtCoder · awc0075_a

A. 山脉之字形

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

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