AT_abc406_c [ABC406C] ~

整数列 $ 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 $ の連続部分列であってチルダ型である数列の個数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

答えを出力せよ。

### Sample Explanation 1 数列 $ (1, 3, 6, 4, 2, 5) $ の連続部分列のうちチルダ型であるものは $ (3, 6, 4, 2, 5) $ , $ (1, 3, 6, 4, 2, 5) $ の $ 2 $ つのみです。 ### Constraints - $ 4 \leq N \leq 3 \times 10^5 $ - $ P = (P_1, P_2, \ldots, P_N) $ は $ (1, 2, \ldots, N) $ を並べ替えて得られる数列 - 入力される値はすべて整数