题目描述

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

如果数组 $a_1, a_2, \dots, a_n$ 中的某个子数组 $a_l, a_{l + 1}, \dots , a_r$ 恰好包含一次从 $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]$ .

请计算子排列的数量。

输入格式

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

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

注意：这个数组可以包含相同的整数。

输出格式

一个整数，表示 $a$ 的子排列数量。

输入输出样例 #1

输入 #1

8
2 4 1 3 4 2 1 2

输出 #1

7

输入输出样例 #2

输入 #2

5
1 1 2 1 2

输出 #2

6

注

第一个样例中有 $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]$ 。

data:by lkj