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