You have an array $a_1, a_2, \dots, a_n$. 

Let's call some subarray $a_l, a_{l + 1}, \dots , a_r$ of this array a subpermutation if it contains all integers from $1$ to $r-l+1$ exactly once. For example, array $a = [2, 2, 1, 3, 2, 3, 1]$ contains $6$ subarrays which are subpermutations: $[a_2 \dots a_3]$, $[a_2 \dots a_4]$, $[a_3 \dots a_3]$, $[a_3 \dots a_5]$, $[a_5 \dots a_7]$, $[a_7 \dots a_7]$.

You are asked to calculate the number of subpermutations.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le n$). 

This array can contain the same integers.


-----Output-----

Print the number of subpermutations of the array $a$.


-----Examples-----
Input
8
2 4 1 3 4 2 1 2

Output
7

Input
5
1 1 2 1 2

Output
6



-----Note-----

There are $7$ subpermutations in the first test case. Their segments of indices are $[1, 4]$, $[3, 3]$, $[3, 6]$, $[4, 7]$, $[6, 7]$, $[7, 7]$ and $[7, 8]$.

In the second test case $6$ subpermutations exist: $[1, 1]$, $[2, 2]$, $[2, 3]$, $[3, 4]$, $[4, 4]$ and $[4, 5]$.

Source: codeforces | Difficulty: VERY_HARD
Tags: String algorithms

Complete search

Divide and conquer

Mathematics

Data structures


Solutions:
import math
mod = int(1000000007)
i = lambda : map(int, input().split())
n = int(input())
a = [int(x) for x in input().split()]
t = [[0] * 21 for i in range(300005)]
for i in range(n):
	t[i][0] = a[i]

def build(n):
	for j in range(1, 20):
		for i in range(n):
			if i + (1 << j) - 1 > n - 1:
				break
			t[i][j] = max(t[i][j - 1], t[i + (1 << j - 1)][j - 1])

def query(p, q):
	(p, q) = (int(p), int(q))
	log = int(math.log2(q - p + 1))
	m = t[p][log]
	n = t[q - (1 << log) + 1][log]
	return max(m, n)
b = [-1] * (n + 2)
build(n)
max1 = -1
ans = 0
for i in range(n):
	max1 = max(max1, b[a[i]])
	b[a[i]] = i
	x = b[1]
	while x > max1:
		if x <= max1:
			break
		p = query(x, i)
		if p == i - x + 1:
			ans += 1
			x = b[p + 1]
		else:
			x = i - p + 1
print(ans)