/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
正整数からなる数列 a = (a_1, \ldots, a_n) が生成可能であるとは，空列からはじめて次の操作の繰り返しで a が得られることをいいます．
- 操作：正整数 k を選び，列の好きな位置に (1, 2, \ldots, k-1, k) を挿入する．より形式的には，列 a = (a_1, \ldots, a_m) に対して 0\leq i\leq m となる整数 i および正整数 k を選び，a を (a_1,\ldots,a_{i}, 1, 2, \ldots, k-1, k, a_{i+1}, \ldots, a_m) に置き換える．
例えば a = (1,2,1,1,2,1,3,4,2,3) は生成可能です．次が生成手順の一例です：
() \to (\boldsymbol{1,2}) \to (1,2,\boldsymbol{1,2,3}) \to (1,2,1,\boldsymbol{1,2,3,4},2,3) \to (1,2,1,1,2,\boldsymbol{1},3,4,2,3)
正整数からなる数列 A = (A_1, \ldots, A_N) が与えられます．次を満たす整数の組 (L, R) の個数を求めてください：
- 1\leq L\leq R\leq N であり，連続部分列 (A_L, \ldots, A_R) は生成可能である．
制約
- 1\leq N\leq 5\times 10^5
- 1\leq A_i\leq N
入力
入力は以下の形式で標準入力から与えられます．
N A_1 \ldots A_N
出力
条件を満たす整数の組 (L, R) の個数を出力してください．
入力例 1
6 1 2 1 2 1 3
出力例 1
11
次の 11 個です：
- (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (3,3), (3,4), (3,5), (3,6), (5,5)
入力例 2
5 1 1 1 1 1
出力例 2
15
すべての連続部分列が生成可能です．
入力例 3
7 1 2 1 2 1 3 4
出力例 3
13
Score : 600 points
Problem Statement
A sequence a = (a_1, \ldots, a_n) consisting of positive integers is said to be generatable when one can obtain a by repeating the following operation on an empty sequence.
- Operation: Choose a positive integer k, and insert (1, 2, \ldots, k-1, k) into some position in the sequence. More formally, for a sequence a = (a_1, \ldots, a_m), choose an integer i such that 0\leq i\leq m and a positive integer k, and replace a with (a_1,\ldots,a_{i}, 1, 2, \ldots, k-1, k, a_{i+1}, \ldots, a_m).
For instance, a = (1,2,1,1,2,1,3,4,2,3) is generatable. Here is one way to generate it:
() \to (\boldsymbol{1,2}) \to (1,2,\boldsymbol{1,2,3}) \to (1,2,1,\boldsymbol{1,2,3,4},2,3) \to (1,2,1,1,2,\boldsymbol{1},3,4,2,3).
You are given a sequence A = (A_1, \ldots, A_N) consisting of positive integers. Find the number of pairs of integers (L, R) such that:
- 1\leq L\leq R\leq N and the contiguous subsequence (A_L, \ldots, A_R) is generatable.
Constraints
- 1\leq N\leq 5\times 10^5
- 1\leq A_i\leq N
Input
The input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print the number of pairs of integers (L, R) satisfying the conditions.
Sample Input 1
6 1 2 1 2 1 3
Sample Output 1
11
Here are the 11 sought pairs:
- (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (3,3), (3,4), (3,5), (3,6), (5,5).
Sample Input 2
5 1 1 1 1 1
Sample Output 2
15
All the contiguous subsequences are generatable.
Sample Input 3
7 1 2 1 2 1 3 4
Sample Output 3
13