codeforces#P1175F. The Number of Subpermutations
The Number of Subpermutations
Description
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.
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.
Print the number of subpermutations of the array $a$.
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$.
Samples
8
2 4 1 3 4 2 1 2
7
5
1 1 2 1 2
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]$.