D. Decinc Dividing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

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

Examples
Input
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
Note

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.