Range Inversion Query

You are given a sequence of length \( n \) and \( m \) queries. For each query, you are given a 1-indexed interval \( [L, R] \), and you need to determine the number of inversion pairs in the subarray \( a[L \ldots R] \). A pair \( (i,j) \) is called an inversion if \( L \le i a_j \).

Note: Inversions are defined based on the original order of the array. The input numbers can be arbitrary and might require coordinate compression.

The formula for an inversion pair is given by:

[ \text{Inversions} = |{ (i,j) \mid L \le i < j \le R,; a_i > a_j }|. ]

inputFormat

The first line contains two integers \( n \) and \( m \). The second line contains \( n \) integers representing the sequence \( a_1, a_2, \ldots, a_n \). Each of the next \( m \) lines contains two integers \( L \) and \( R \) (1-indexed), denoting a query for the number of inversion pairs in the subarray \( a[L \ldots R] \).

outputFormat

For each query, output a single integer: the number of inversion pairs in the specified interval.

sample

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

3
0
1