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.

Source: codeforces | Difficulty: VERY_HARD
Tags: Greedy algorithms

Complete search

Dynamic programming

Divide and conquer

Data structures


Solutions:
input = __import__('sys').stdin.readline
n = int(input())
a = list(map(int, input().split())) + [n + 1]
cache = {}

def check(i, u, d):
	keys = []
	j = i
	while j + 1 <= n:
		key = (j, u, d)
		v = cache.get(key, -1)
		if v != -1:
			j = v
			break
		keys.append(key)
		if u < a[j] < d:
			if a[j] < a[j + 1]:
				u = max(u, a[j])
			elif a[j] > a[j + 1]:
				d = min(d, a[j])
		elif u < a[j]:
			u = a[j]
		elif d > a[j]:
			d = a[j]
		else:
			break
		j += 1
	for key in keys:
		cache[key] = j
	return j
ans = 0
for i in range(n):
	u = 0
	d = n + 1
	j = check(i, u, d)
	ans += j - i
print(ans)