问题1102--差异对数

1102: 差异对数

时间限制: 1 Sec  内存限制: 128 MB
提交: 90  解决: 33
[提交] [状态] [讨论版] [命题人:]

题目描述

BSNY在解决一个难题,这个难题是这样的。给你n个整数a1, a2, …, an 可以定义一个函数f(l, r, x), 能范围在区间[l, r]范围内,有多少个数字等于x。公式化的说: 统计满足 l<=k<=r 同时 ak=x 的数量。现在问题,在这个序列中,有多少对i, j 满足 1<=i<j<=n 同时 f(1, i, ai) > f(j, n, aj)

输入

输入n

然后输入n个整数

输出

输出答案

样例输入 Copy

7
1 2 1 1 2 2 1

样例输出 Copy

8

提示

【样例说明】

其他样例:

输入:

3

1 1 1

输出:

1

 

输入:

5

1 2 3 4 5

输出:

0

 

【数据规模和约定】

1<=n<=10^6   1<=ai<=10^9

来源/分类

cf459D