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 a1,?a2,?...,?an. Let's denote f(l,?r,?x) the number of indices k such that: l?≤?k?≤?r and ak?=?x. His task is to calculate the number of pairs of indicies i,?j (1?≤?i??f(j,?n,?aj).
Help Pashmak with the test.
Input
The first line of the input contains an integer n (1?≤?n?≤?106). The second line contains n space-separated integers a1,?a2,?...,?an (1?≤?ai?≤?109).
Output
Print a single integer ? the answer to the problem.
Sample test(s)
Input
71 2 1 1 2 2 1
Output
Input
31 1 1
Output
Input
51 2 3 4 5
Output
题目给出的F函数,可以用离散的方法加预处理 将每个F(1,i,x)和F(j,n,x)求出,分别保存于f1, f2数组,那么题目就可以转化为: f1[i] > f2[j] && i
#include#include #include #include #include #include #define lson o > 1; if(fu[m] >= v) y = m; else x = m+1; } return x;}void up(int o) { num[o] = num[o> 1; if(a > 1; LL res = 0; if(a > n; for(int i = 0; i = 0; i--) { int tmp = bs(tt[i], 0, k-1); vis[tmp]++; f2[i] = vis[tmp]; b = max(b, f2[i]); } LL ans = 0; for(int i = 0; i
??
已抢23080个
抢已抢117483个
抢已抢139072个
抢已抢6149个
抢已抢34801个
抢已抢7648个
抢