题目描述

对于一个整数序列
$A = (A_1, A_2, \dots, A_{|A|})$，如果它满足以下 四个条件，则称该序列为波浪形（tilde-shaped）序列：

1. 序列长度 $|A| \ge 4$；
2. $A_1 < A_2$；
3. 存在恰好一个整数 $i$（$2 \le i < |A|$），使得：
   $A_{i-1} < A_i > A_{i+1}$（即存在唯一一个"峰"）；
4. 存在恰好一个整数 $i$（$2 \le i < |A|$），使得：
   $A_{i-1} > A_i < A_{i+1}$（即存在唯一一个"谷"）。

现在给定一个长度为 $N$ 的排列
$P = (P_1, P_2, \dots, P_N)$，其中包含 $1$ 到 $N$ 的所有整数且不重复。

请你计算：有多少个连续子数组是波浪形序列。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $P_1, P_2, \dots, 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

数据范围

• $4 \le N \le 3 \times 10^5$
• $P$ 是 $(1,2,\dots,N)$ 的一个排列