### Sherlock and Inversions

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.

### Limits

- 1 ≤
`A`_{i} ≤ 10^{9}
- 1 ≤
`L`_{i} ≤ `R`_{i} ≤ `N`

Subtask 1 (20%): 1 ≤ `N`, `Q` ≤ 10^{3}

Subtask 2 (20%): 1 ≤ `N` ≤ 10^{3} and 1 ≤ `Q` ≤ 10^{5}

Subtask 3 (60%): 1 ≤ `N`, `Q` ≤ 10^{5}

Subtask 4 (0%): Sample

### Sample Input 1

5 3
1 4 2 3 1
1 2
3 5
1 5

### Sample Output 1

0
2
5

### Explanation

query1: Number of inversions in B = [1, 4] is 0.

query2: Number of inversions in B = [2, 3, 1] is 2 since B[0]>B[2] and B[1]>B[2].

query3: Number of inversions in original array is 5.