题目描述

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$，并且定义函数 $f(l, r)$ 如下：

• $f(l, r)$ 表示子序列 $(A_l, A_{l+1}, \ldots, A_r)$ 中不同元素的种类数。

求下式的值：

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

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

一个整数，表示答案。

输入样例 #1

3
1 2 2

输出样例 #1

8

输入样例 #2

9
5 4 2 2 3 2 4 4 1

输出样例 #2

111

提示

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• 输入的数值均为整数

样例解释 1

以 $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$ 的总和为 8。

翻译使用 ChatGPT。