D. Decinc Dividingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet'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. InputThe 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.OutputOutput 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)ExamplesInput
3
2 3 1
Output
6
Input
6
4 5 2 6 1 3
Output
19
Input
10
7 10 1 8 3 9 2 4 6 5
Output
39
NoteIn 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.
3
2 3 1

6 
['brute force', 'data structures', 'divide and conquer', 'dp', 'greedy', '*2800']