I have tried to solve the problem of finding k-interesting pairs [here].(http://mirror.codeforces.com/contest/769/submission/26220768)

My solution is quadratic O(n^2). If it is run on the sequence of numbers given, then n = 10^5 at most. I have followed the trick of the editorial and built an array of the frequencies of each element. This happens in O(n) time, with n = 10^5, at most

And have then applied the quadratic time algorithm on the frequency array so now n = 10^4. However, this isn't enough to get past the time limit.

What are further optimizations I can perform ?