问题 H: Insert 1, Insert 2, Insert 3, ...

A sequence a1, a2, . . . , an consisting of positive integers is said to be generatable when one can obtain a by repeating the following operation on an empty sequence: • Choose a positive integer k, and insert 1, insert 2, ..., insert k respectively into some position in the sequence while preserving their relative order. More specifically, let ix be the index of newly inserted x in the sequence after the operation, then i1 < i2 < · · · < ik. For instance, a = (1, 1, 2, 2, 1, 1, 3, 4, 2, 3) is generatable. Here is one way to generate it: () → (1, 2) → (1, 2, 1, 2, 3) → (1, 1, 2, 2, 1, 3, 4, 2, 3) → (1, 1, 2, 2, 1, 1, 3, 4, 2, 3). You are given a sequence A1, A2, . . . , AN consisting of positive integers. Find the number of pairs of integers (L, R) such that: • 1 ≤ L ≤ R ≤ N and the contiguous subsequence AL, . . . , AR is generatable.

The first line contains an integer N (1 ≤ N ≤ 106 ). The second line contains N integers A1, A2, . . . , AN (1 ≤ Ai ≤ N).

Output the number of pairs of integers (L, R) satisfying the conditions. 

6
1 1 2 2 3 3

8

In the first sample, the 8 pairs are: (1, 1),(1, 2),(1, 3),(1, 4),(1, 5),(1, 6),(2, 2),(2, 3).