分数: 350 点
问题陈述
对于整数序列 A = (A_1, A_2, \ldots, A_{|A|}),我们说 A is 波浪线形 如果满足以下所有四个条件:
- 长度 |A| 至少 4.
- A_1 < A_2.
- 恰好存在一个整数 i 与 2 \leq i < |A| 这样 A_{i-1} < A_i > A_{i+1}.
- 恰好存在一个整数 i 与 2 \leq i < |A| 这样 A_{i-1} > A_i < A_{i+1}.
给你一个排列 P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N)。查找(连续)子数组的数量 P 是波浪号形状的。
约束
- 4 \leq N \leq 3 \times 10^5
- P = (P_1, P_2, \ldots, P_N) 是一个排列 (1, 2, \ldots, N).
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \ldots P_N
输出
输出答案。
示例输入 1
6 1 3 6 4 2 5
示例输出 1
2
的子数组中 (1, 3, 6, 4, 2, 5),正好有两个是波浪号形状的: (3, 6, 4, 2, 5) 和 (1, 3, 6, 4, 2, 5).
示例输入 2
6 1 2 3 4 5 6
示例输出 2
0
示例输入 3
12 11 3 8 9 5 2 10 4 1 6 12 7
示例输出 3
4