我讨厌 Sigma 问题

题目描述

给定长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$。

定义 $f(l, r)$ 为：

子序列 $(A_l, A_{l+1}, \ldots, A_r)$ 中不同数值的个数。

请计算下式的值：

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

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出答案。

样例

3
1 2 2

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

9
5 4 2 2 3 2 4 4 1

111

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$
• 输入中的所有数值均为整数