D. Pashmak 与 Parmida 的问题

每次测试的时间限制：$3$ 秒
内存限制：$256$ 兆字节

Parmida 是一个聪明的女孩，她想要参加今年的奥林匹克竞赛。当然，她也希望她的搭档是聪明的（尽管他并不聪明）！Parmida 为 Pashmak 准备了以下测试问题。

有一个由 $n$ 个整数 $a_1, a_2, \dots, a_n$ 组成的序列 $a$。记 $f(l, r, x)$ 为满足 $l \le k \le r$ 且 $a_k = x$ 的下标 $k$ 的个数。Pashmak 的任务是计算有多少对下标 $(i, j)$（$1 \le i < j \le n$）满足：

请帮助 Pashmak 完成这个测试。

输入

第一行包含一个整数 $n$（$1 \le n \le 10^6$）。
第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

输出

输出一个整数 —— 问题的答案。

示例

示例 $1$：

输入：

7
1 2 1 1 2 2 1

输出：

8

示例 $2$：

输入：

3
1 1 1

输出：

1

示例 $3$：

输入：

5
1 2 3 4 5

输出：

0