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

链接：https://ac.nowcoder.com/acm/contest/57362/H
来源：牛客网
A sequence a1,a2,…,ana_1, a_2, \ldots, a_na1,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 ixi_xix be the index of newly inserted $x$ in the sequence after the operation, then i1<i2<⋯<iki_1 < i_2 < \cdots < i_ki1<i2<⋯<ik.

For instance, $a=(1,1,2,2,1,1,3,4,2,3)$ is generatable. Here is one way to generate it:

$()\to (\text{1},\text{2})\to (1,2,\text{1},\text{2},\text{3})\to (1,\text{1},2,\text{2},1,\text{3},\text{4},2,3)\to (1,1,2,2,\text{1},1,3,4,2,3)$.

You are given a sequence A1,A2,…,ANA_1, A_2, \ldots, A_NA1,A2,…,AN consisting of positive integers. Find the number of pairs of integers (L,R)(L, R)(L,R) such that:

•   1≤L≤R≤N1 \le L \le R \le N1≤L≤R≤N and the contiguous subsequence AL,…,ARA_L,\ldots,A_RAL,…,AR is generatable.

The first line contains an integer $N$ (1≤N≤1061 \le N \le 10^61≤N≤106).
The second line contains $N$ integers A1,A2,…,ANA_1,A_2,\ldots,A_NA1,A2,…,AN (1≤Ai≤N1 \le A_{i} \le N1≤Ai≤N).

Output the number of pairs of integers (L,R)(L,R)(L,R) satisfying the conditions.
样例输入1：
6
1 2 1 2 1 3
样例输出1：
11

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