你有一个数组 $$$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]$$$。