一个序列问题

rt，给定一个序列 $a_i$，多次询问 $l,r$，求 $\sum_{i=1}^l \sum_{j=1}^r [a_i=a_j]$ 有没有优于 $O(n^2)$ 的在线做法或者优于 $O(n\sqrt n)$ 的离线做法？