First reformulate the problem into counting equal pairs rather than unequal pairs. Split into blocks of size $B$. We can maintain block_ans[i][j] which stores the answer for all the blocks in the range $[i, j]$ (there are $\frac{n^2}{B^2}$ such ranges), and block_prefcnt[i][j] which stores for each value $i$, its count in the first $j$ blocks. They can be updated in $O(\frac{n^2}{B^2} + \frac{n}{B})$ and using those values you can do queries in $O(B)$ (the idea is similar to square root decomposition). Then you just need to choose the right value of $B$, if you let it be about $n^{\frac{2}{3}}$ then the complexity is $O((n + q) \cdot n^{\frac{2}{3}})$ (I just fixed it to $1000$ though and that was fast enough).
First reformulate the problem into counting equal pairs rather than unequal pairs. Split into blocks of size $B$. We can maintain
block_ans[i][j]which stores the answer for all the blocks in the range $[i, j]$ (there are $\frac{n^2}{B^2}$ such ranges), andblock_prefcnt[i][j]which stores for each value $i$, its count in the first $j$ blocks. They can be updated in $O(\frac{n^2}{B^2} + \frac{n}{B})$ and using those values you can do queries in $O(B)$ (the idea is similar to square root decomposition). Then you just need to choose the right value of $B$, if you let it be about $n^{\frac{2}{3}}$ then the complexity is $O((n + q) \cdot n^{\frac{2}{3}})$ (I just fixed it to $1000$ though and that was fast enough).