CF459D.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.

帕尔米达是一个聪明的女孩，她今年想参加奥林匹克竞赛。当然，她也希望自己的搭档同样聪明（尽管他其实并不聪明）！帕尔米达为帕什马克准备了如下测试题。

给定一个由 $n$ 个整数 $a_1, a_2, ..., a_n$ 组成的序列 $a$。定义函数 $f(l, r, x)$ 表示满足 $l ≤ k ≤ r$ 且 $a_k = x$ 的下标 $k$ 的个数。他的任务是计算满足如下条件的下标对 $(i, j)$（其中 $1 ≤ i < j ≤ n$）的个数：

$$f(1, i, a_i) > f(j, n, a_j).$$

请帮助帕什马克解决这道测试题。

The first line of the input contains an integer n (1 ≤ n ≤ 106). The second line contains n space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109).

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

Print a single integer — the answer to the problem.

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