给定一个包含 $N$ 个自然数 $a_i$ ($1 \le a_i \le N$) 的序列。
请问有多少对数字 $l$ 和 $r$ ($1 \le l \le r \le N$)，使得从第 $l$ 位到第 $r$ 位的连续子序列是 $1$ 到 $r - l + 1$ 的一个排列？
输入格式
第一行包含一个自然数 $N$，表示给定序列的长度。
第二行包含数字 $a_1, a_2, \dots, a_N$，依次表示序列中的值。对于所有 $i = 1, 2, \dots, N$，满足 $1 \le a_i \le N$。
输出格式
在唯一的一行中输出符合上述条件的子序列个数。
子任务
在所有子任务中，均满足 $1 \le N \le 10^6$。
| 子任务 | 分值 | 限制 |
|---|---|---|
| 1 | 13 | $1$ 到 $N$ 的每个数字在序列中恰好出现一次。 |
| 2 | 20 | $N \le 5000$ |
| 3 | 33 | $N \le 50000$ |
| 4 | 34 | 无额外限制。 |
样例
输入 1
3 3 1 2
输出 1
3
输入 2
5 3 2 1 2 3
输出 2
5
输入 3
7 2 1 3 1 2 3 4
输出 3
8
说明
第三个样例的解释： 构成排列的子序列对应的 $(l, r)$ 对为：
$(l, r) = (2, 2) : 1$ $(l, r) = (1, 2) : 2, 1$ $(l, r) = (1, 3) : 2, 1, 3$ $(l, r) = (4, 4) : 1$ $(l, r) = (4, 5) : 1, 2$ $(l, r) = (4, 6) : 1, 2, 3$ $(l, r) = (4, 7) : 1, 2, 3, 4$ $(l, r) = (3, 5) : 3, 1, 2$