AT_abc406_c [ABC406C] ~

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.

The input is given from Standard Input in the following format: > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

Output the answer.

### Sample Explanation 1 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) $ . ### 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.