CF1693D Decinc Dividing

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) $

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.