Decinc Dividing

### 题目描述 定义一个序列 $a$ 是好的，仅当可以通过删除 $a$ 的一个单调递减子序列（可以为空）使得 $a$ 单调递增。 给定一个 $1\sim n$ 的排列 $p$，你需要求出 $p$ 有多少子段是好的。 ### 输入格式 第一行输入一个整数 $n(1\leq n\leq2\times10^5)$。 接下来一行输入 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$，保证 $p_i$ 互不相同。 ### 输出格式 输出一行一个整数表示好的子段个数。 ### 样例解释 对于样例一，所有 $p$ 的子段都是好的。 对于样例二： - 例如 $p[1,5]$ 是好的，因为 $\{4,5,2,6,1\}$ 可以通过删除单调递减子序列 $\{4,2,1\}$ 得到一个单调递增序列 $\{5,6\}$。 - 事实上，除了 $p[1,6],p[2,6]$ 之外的所有子段都是好的。

Let's call an array $ a $ of $ m $ integers $ a_1, a_2, \ldots, a_m $ Decinc if $ a $ can be made increasing by removing a decreasing subsequence (possibly empty) from it. - For example, if $ a = [3, 2, 4, 1, 5] $ , we can remove the decreasing subsequence $ [a_1, a_4] $ from $ a $ and obtain $ a = [2, 4, 5] $ , which is increasing. You are given a permutation $ p $ of numbers from $ 1 $ to $ n $ . Find the number of pairs of integers $ (l, r) $ with $ 1 \le l \le r \le n $ such that $ p[l \ldots r] $ (the subarray of $ p $ from $ l $ to $ r $ ) is a Decinc array.

The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the size of $ p $ . The second line contains $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ , all $ p_i $ are distinct) — elements of the permutation.

Output the number of pairs of integers $ (l, r) $ such that $ p[l \ldots r] $ (the subarray of $ p $ from $ l $ to $ r $ ) is a Decinc array. $ (1 \le l \le r \le n) $

3
2 3 1

6

6
4 5 2 6 1 3

19

10
7 10 1 8 3 9 2 4 6 5

39

In the first sample, all subarrays are Decinc. In the second sample, all subarrays except $ p[1 \ldots 6] $ and $ p[2 \ldots 6] $ are Decinc.