I. Permutations again
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a sequence Ai consisting of N integers. Find the number of pairs (L, R) for which the subsegment {AL, AL + 1, ..., AR} is a permutation of R - L + 1 numbers.

A permutation of K numbers is any sequence of numbers from 1 to K, where each element occurs only once.

Input

The first line contains number N — a sequence length. The second line contains N integers — sequence Ai elements.

1 ≤ N ≤ 106
1 ≤ Ai ≤ N
Output

Print the number of pairs (L, R), fulfilling the condition.

Example
Input
3
3 1 2
Output
3