You are given a sequence of $N$ natural numbers $a_i$ ($1 \le a_i \le N$).
How many pairs of numbers $l$ and $r$ ($1 \le l \le r \le N$) exist such that the contiguous subsequence from the $l$-th to the $r$-th position is a permutation of the numbers from $1$ to $r - l + 1$?
Input
The first line contains a natural number $N$, the length of the given sequence. The second line contains the numbers $a_1, a_2, \dots, a_N$, the values of the sequence in order. It holds that $1 \le a_i \le N$ for all $i = 1, 2, \dots, N$.
Output
In a single line, print the required number of subsequences that form a permutation of the specified form.
Subtasks
In all subtasks, $1 \le N \le 10^6$.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 13 | Each number from $1$ to $N$ appears exactly once in the sequence. |
| 2 | 20 | $N \le 5000$ |
| 3 | 33 | $N \le 50000$ |
| 4 | 34 | No additional constraints. |
Examples
Input 1
3 3 1 2
Output 1
3
Input 2
5 3 2 1 2 3
Output 2
5
Input 3
7 2 1 3 1 2 3 4
Output 3
8
Note
Explanation of the third example: The pairs $(l, r)$ that determine a subsequence which is a permutation are:
$(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$