### Sherlock and Inversions

Watson gives to Sherlock an array of N integers denoted by A1, A2 ... AN.
Now he gives him Q queries of form Li, Ri. For each such query Sherlock has to report the number of inversions in subarray denoted by [Li, Ri].

Inversions in a subarray denoted by [a, b] are number of pairs (i, j) such that ai < jb and Ai > Aj.

### 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 Li, Ri.

### Output

For each query, print the required answer in one line.

### Limits

• 1 ≤ Ai ≤ 109
• 1 ≤ LiRiN

Subtask 1 (20%): 1 ≤ N, Q ≤ 103

Subtask 2 (20%): 1 ≤ N ≤ 103 and 1 ≤ Q ≤ 105

Subtask 3 (60%): 1 ≤ N, Q ≤ 105

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

```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>B and B>B.

query3: Number of inversions in original array is 5.

### Submitting .cpp to 'sherlockinversions'

Time Limit: 5 Seconds
Memory Limit: 256MB
No. of ACs: 52