← 返回题目列表

AtCoder · arc206_a

A. 范围替换

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

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