← 返回题目列表

AtCoder · abc371_e

H. 我讨厌西格玛问题

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

分数: 475 点

问题陈述

给你一个整数序列 A = (A_1, A_2, \ldots, A_N) 长度 N。 定义 f(l, r) 为:

  • 子序列中不同值的数量 (A_l, A_{l+1}, \ldots, A_r).

计算以下表达式:

\displaystyle \sum_{i=1}^{N}\sum_{j=i}^N f(i,j).


约束

  • 1\leq N\leq 2\times 10^5
  • 1\leq A_i\leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 \ldots A_N

输出

打印答案。


样本输入 1

3
1 2 2

示例输出 1

8

考虑 f(1,2)。子序列 (A_1, A_2) = (1,2) 包含 2 不同的值,所以 f(1,2)=2.

考虑 f(2,3)。子序列 (A_2, A_3) = (2,2) 包含 1 不同的值,所以 f(2,3)=1.

总和 f is 8.


示例输入 2

9
5 4 2 2 3 2 4 4 1

示例输出 2

111