← 返回题目列表

AtCoder · agc063_b

B. 插入 1、2、3、...

中文机器翻译题面 查看原题

分数: 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