sherlockinversions

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

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.


Submitting to 'sherlockinversions'


You're not logged in! Click here to login


Submitting to 'sherlockinversions'


You're not logged in! Click here to login


Submitting .cpp to 'sherlockinversions'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 5 Seconds
Memory Limit: 256MB
No. of ACs: 37
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 20
2 20
3 60
4 0