The Number of Subpermutations

题意翻译

给定数组$a_1,a_2 \cdots a_n$，若子序列$a_l,a_{l+1}\cdots a_{r}$满足$1,2\cdots r-l+1$所有整数各出现一次，则称其为这个数组的一个子排列。求这个数组子排列个数

题目描述

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

输入输出样例

输入样例 #1

8
2 4 1 3 4 2 1 2

输出样例 #1

7

输入样例 #2

5
1 1 2 1 2

输出样例 #2

6

说明

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