← 返回题目列表

AtCoder · abc406_c

E. 波浪序列

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

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