Description

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

Input

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.

Output

Print the number of subpermutations of the array $a$.

Samples

8
2 4 1 3 4 2 1 2

7

5
1 1 2 1 2

6

Note

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