406014 - 子排列计数

给定一个长度为 n 的数组 a₁, a₂, …, aₙ。 如果数组的一个子数组 al, al+1, …, ar 恰好包含从 1 到 r − l + 1 的所有整数各一次，则称它为 “子排列”。 求数组 a 的子排列数量。

第一行一个整数 n（（1 ≤ n ≤ 3 × 10⁵））。 第二行 n 个整数，表示数组 a（1 ≤ aᵢ ≤ n）。

输出合法子区间的数量。

第一个测试用例中有 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]。