CF1175F.The Number of Subpermutations

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.

你有一个数组 $a_1, a_2, \dots, a_n$。

我们称该数组的某个子数组 $a_l, a_{l + 1}, \dots , a_r$ 为子排列（subpermutation），当且仅当它恰好包含从 $1$ 到 $r-l+1$ 的所有整数各一次。例如，数组 $a = [2, 2, 1, 3, 2, 3, 1]$ 包含 $6$ 个子排列：$[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]$。

你需要计算子排列的总数。

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.

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots , a_n$（$1 \le a_i \le n$）。

该数组中可能包含相同的整数。

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

输出数组 $a$ 的子排列数量。

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]$.

第一个测试用例中有 $7$ 个子排列，它们的下标区间分别为 $[1, 4]$、$[3, 3]$、$[3, 6]$、$[4, 7]$、$[6, 7]$、$[7, 7]$ 和 $[7, 8]$。

第二个测试用例中存在 $6$ 个子排列：$[1, 1]$、$[2, 2]$、$[2, 3]$、$[3, 4]$、$[4, 4]$ 和 $[4, 5]$。