#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### 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`. For each such query Sherlock has to report the number of inversions in subarray denoted by

_{i}, R_{i}`[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`≤ 10_{i}^{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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 20 | 10 | 5s | 256MB | Minimum |

2 | 20 | 10 | 5s | 256MB | Minimum |

3 | 60 | 10 | 5s | 256MB | Minimum |

4 | 0 | 1 | 5s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o sherlockinversions -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512