分数: 600 点
问题陈述
一个序列 a = (a_1, \ldots, a_n) 由正整数组成,据说是 可生成 何时可以获得 a 通过在空序列上重复以下操作。
- 操作:选择一个正整数 k,然后插入 (1, 2, \ldots, k-1, k) 进入序列中的某个位置。更正式地说,对于一个序列 a = (a_1, \ldots, a_m),选择一个整数 i 这样 0\leq i\leq m 和一个正整数 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