Pashmak and Parmida's problem

3000ms

262144K

Description:

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₁, a₂, ..., 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.

Input:

The first line of the input contains an integer n (1 ≤ n ≤ 10⁶). The second line contains n space-separated integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Output:

Print a single integer — the answer to the problem.

Sample Input:

7
1 2 1 1 2 2 1

Sample Output:

Sample Input:

3
1 1 1

Sample Output:

Sample Input:

5
1 2 3 4 5

Sample Output:

Informação

Provedor Codeforces

Código CF459D