A9647. Pashmak and Parmida's problem

Parmida is a clever girl and she wants to participate in Olympiads this year. Of course she wants her partner to be clever too (although he's not)! Parmida has prepared the following test problem for Pashmak.

There is a sequence $a$ that consists of $n$ integers $a_{1},a_{2},...,a_{n}$ . Let's denote $f(l,r,x)$ the number of indices $k$ such that: $l<=k<=r$ and $a_{k}=x$ . His task is to calculate the number of pairs of indicies $i,j$ $(1<=i<j<=n)$ such that $f(1,i,a_{i})>f(j,n,a_{j})$ .

Help Pashmak with the test.
帕米达是个聪明的女孩，今年她想参加奥林匹克竞赛。当然，她希望她的搭档也很聪明(虽然他并不聪明)！帕尔米达为帕什马克准备了以下测试题。

有一个序列 a 由 n 个整数$a_{1},a_{2},...,a_{n}$组成。让我们用 $f(l,r,x)$ 表示这样的索引 k 的个数： $l<=k<=r$ 和 $a_{k}=x$ 。他的任务是计算 i, j 和 $i,j$ $(1<=i \lt j<=n)$这两个索引的对数。 $(1<=i \lt j<=n)$ 中 $f(1,i,a_{i}) \gt f (j,n,a_{j})$ 的个数。

帮助 Pashmak 完成测试。

The first line of the input contains an integer $n$ $(1<=n<=10^{6})$ . The second line contains $n$ space-separated integers $a_{1},a_{2},...,a_{n}$ $(1<=a_{i}<=10^{9})$ .
输入
输入的第一行包含一个整数 $n$ $(1<=n<=10^{6})$ .第二行包含 n 个空格分隔的整数 $a_{1},a_{2},...,a_{n}$ $(1<=a_{i}<=10^{9})$

Print a single integer — the answer to the problem.
输出
打印一个整数--问题的答案。