sherlockinversions

Sherlock and Inversions

Watson gives to Sherlock an array of N integers denoted by A₁, A₂ ... 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⁹
• 1 ≤ L_i ≤ R_i ≤ N

Subtask 1 (20%): 1 ≤ N, Q ≤ 10³

Subtask 2 (20%): 1 ≤ N ≤ 10³ and 1 ≤ Q ≤ 10⁵

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

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.