强烈谴责北京市海淀区中小学生信息学竞赛出题组

T1 pair

元旦联欢会，班里有 $n$ 个同学，老师统计每个同学最喜欢哪种零食，零食以整数编号，成一个长度为 $n$ 的数组 $a$。

定义一个序列的价值是序列中相等的无序数对数量，如 $[1,1,2,2,1]$ 里的相等的数对下标分别是 $(1,2),(1,5),(2,5),(3,4)$ ，它的价值就是 $4$。

现在老师为了统计同学们最喜欢吃的零食（雾，为啥统计 fav 要算这样的东西，还是子段上的？），所以要（smart as+）你来帮她计算原数组的所有子段的价值和。

输入样例

CPP

4
1 1 2 1

输出样例

CPP

6

$1\le n\le10^5$

subtask $a_i$ 相等