CF1175F The Number of Subpermutations

给定一个数组 $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]$。 请你计算数组 $a$ 的子排列的数量。

第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。 该数组中的整数可以重复。

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

第一个测试用例中有 $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]$。 由 ChatGPT 4.1 翻译