Why I did not solve it

  1. I did realize that the problem can be transformed into, given number a[i], how many numbers a[j] < a[i] while j < i

  2. I also realize that we can use some sort of segment-tree DS to solve the problem above. But I didn’t have enough experience with such DS

Official answer

1. compress the values to 0 and N 

2. Use a fenwick tree, here we can calculate prefix sum, in this case, total number of elements < compress value,  quickly with update supported, and add answer to the final answer