/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
整数列 A = (A_1, A_2, \ldots, A_{|A|}) に対し、A が チルダ型 とは以下の 4 つの条件をすべて満たすことであると定義します。
- A の長さ |A| は 4 以上である
- A_1 < A_2 である
- A_{i - 1} < A_i > A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である
- A_{i - 1} > A_i < A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である
数列 (1, 2, \ldots, N) を並べ替えて得られる数列 P = (P_1, P_2, \ldots, P_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 つのみです。
入力例 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
Score : 350 points
Problem Statement
For an integer sequence A = (A_1, A_2, \ldots, A_{|A|}), we say that A is tilde-shaped if it satisfies all of the following four conditions:
- The length |A| is at least 4.
- A_1 < A_2.
- There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} < A_i > A_{i+1}.
- There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} > A_i < A_{i+1}.
You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N). Find the number of (contiguous) subarrays of P that are tilde-shaped.
Constraints
- 4 \leq N \leq 3 \times 10^5
- P = (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
Output the answer.
Sample Input 1
6 1 3 6 4 2 5
Sample Output 1
2
Among the subarrays of (1, 3, 6, 4, 2, 5), exactly two are tilde-shaped: (3, 6, 4, 2, 5) and (1, 3, 6, 4, 2, 5).
Sample Input 2
6 1 2 3 4 5 6
Sample Output 2
0
Sample Input 3
12 11 3 8 9 5 2 10 4 1 6 12 7
Sample Output 3
4