← 返回题目列表

Codeforces · 1175/F

F. 子排列数

中文机器翻译题面 查看原题

你有一个数组 $$$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 \点 a_7]$$$、$$$[a_7 \点 a_7]$$$。

系统要求您计算子排列的数量。

输入

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

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

该数组可以包含相同的整数。

输出

打印数组 $$$a$$$ 的子排列数。

示例

输入 #1

8
2 4 1 3 4 2 1 2

输出 #1

7

输入 #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]$$$。