Dylans loves sequence

Dylans is given $N$ numbers $a[1]....a[N]$ And there are $Q$ questions. Each question is like this $(L,R)$ his goal is to find the “inversions” from number $L$ to number $R$. more formally,his needs to find the numbers of pair（$x,y$）, that $L \leq x,y \leq R$ and $x < y$ and $a[x] > a[y]$

In the first line there is two numbers $N$ and $Q$. Then in the second line there are $N$ numbers:$a[1]..a[N]$ In the next $Q$ lines,there are two numbers $L,R$ in each line. $N \leq 1000, Q \leq 100000, L \leq R, 1 \leq a[i] \leq 2^{31}-1$

For each query,print the numbers of "inversions”

You shouldn't print any space in each end of the line in the hack data.