SOLVE
LATER
Watson gives to Sherlock an array of N integers denoted by A_{1}, A_{2} ... A_{N}.
Now he gives him Q queries of form L_{i}, R_{i}. For each such query Sherlock has to report the number of inversions in subarray denoted by [L_{i}, R_{i}].
Inversions in a subarray denoted by [a, b] are number of pairs (i, j) such that a ≤ i < j ≤ b and A_{i} > A_{j}.
Input
First line contains N and Q. Next line contains N space separated integers denoting array A.
Each of the next Q lines contain two space separated integers denoting L_{i}, R_{i}.
Output
For each query, print the required answer in one line.
Constraints
20% files: 1 ≤ N, Q ≤ 10^{3}
20% files: 1 ≤ N ≤ 10^{3} and 1 ≤ Q ≤ 10^{5}
60% files: 1 ≤ N, Q ≤ 10^{5}
1 ≤ A_{i} ≤ 10^{9}
1 ≤ L_{i} ≤ R_{i} ≤ N
query1: Number of inversions in B = [1, 4] is 0.
query2: Number of inversions in B = [2, 3, 1] are 2 since B[0]>B[2] and B[1]>B[2].
query3: Number of inversions in original array are 5.