Let's loop over the permutation, starting from the end, and maintain the array $$$was$$$ where $$$was[x] = 1$$$ if value $$$x$$$ was already visited, otherwise $$$was[x] = 0$$$. At each step you need to find the number pairs $$$(i,j)$$$ such that $$$ i \lt j \ \&\& \ p[i] \gt p[j] $$$ holds. This equals to $$$\sum_{x=1}^{p[i]-1} was[x]$$$. Finally, note that you can use segment tree to maintain the array $$$was$$$ efficiently.