405867: GYM102136 I Permutations again

Memory Limit：256 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

I. Permutations againtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

ExampleInput
3
3 1 2
Output
3

Source/Category

加入题单

上一题 下一题 算法标签：