# [Solution] Decinc Dividing solution codeforces

Decinc Dividing solution codeforces – Let’s call an array 𝑎a of 𝑚m integers 𝑎1,𝑎2,,𝑎𝑚a1,a2,…,am Decinc if 𝑎a can be made increasing by removing a decreasing subsequence (possibly empty) from it.

## [Solution] Decinc Dividing solution codeforces

• For example, if 𝑎=[3,2,4,1,5]a=[3,2,4,1,5], we can remove the decreasing subsequence [𝑎1,𝑎4][a1,a4] from 𝑎a and obtain 𝑎=[2,4,5]a=[2,4,5], which is increasing.

You are given a permutation 𝑝p of numbers from 11 to 𝑛n. Find the number of pairs of integers (𝑙,𝑟)(l,r) with 1𝑙𝑟𝑛1≤l≤r≤n such that 𝑝[𝑙𝑟]p[l…r] (the subarray of 𝑝p from 𝑙l to 𝑟r) is a Decinc array.

Input

The first line contains a single integer 𝑛n (1𝑛21051≤n≤2⋅105)  — the size of 𝑝p.

The second line contains 𝑛n integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn (1𝑝𝑖𝑛1≤pi≤n, all 𝑝𝑖pi are distinct)  — elements of the permutation.

## [Solution] Decinc Dividing solution codeforces

Output the number of pairs of integers (𝑙,𝑟)(l,r) such that 𝑝[𝑙𝑟]p[l…r] (the subarray of 𝑝p from 𝑙l to 𝑟r) is a Decinc array. (1𝑙𝑟𝑛)(1≤l≤r≤n)

Examples
input

Copy
3
2 3 1

output

Copy
6

input

Copy
6
4 5 2 6 1 3


## [Solution] Decinc Dividing solution codeforces

output

Copy
19

input

Copy
10
7 10 1 8 3 9 2 4 6 5

output

Copy
39

Note

In the first sample, all subarrays are Decinc.

In the second sample, all subarrays except 𝑝p[1…6] and 𝑝p[2…6] are Decinc.