分数: 400 点
问题陈述
给你一个序列 A=(A_1,\ldots,A_N) 长度 N。您只需执行一次以下操作。
- 选择一对整数 (L,R) 这样 1\leq L \leq R \leq N。替换每个 A_L,A_{L+1},\ldots,A_R 与 A_L.
可能有多少种不同的序列 A 手术后?
约束
- 所有输入值均为整数。
- 1 \leq N \leq 10^6
- 1\leq A_i \leq N
输入
输入由标准输入按以下格式给出:
N A_1 \ldots A_N
输出
输出答案。
样本输入 1
4 1 1 2 3
示例输出 1
4
操作后可能的顺序为以下四种顺序:
- (1,1,1,1)
- (1,1,1,3)
- (1,1,2,2)
- (1,1,2,3)
例如, (1,1,1,3) 可以通过执行以下操作获得 L=2,R=3.
示例输入 2
10 2 5 6 5 2 1 7 9 7 2
示例输出 2
41