Range Inversion Query

Given a sequence \(a_1,a_2,\dots,a_n\) of length \(n\) and \(m\) queries. Each query provides an interval \([l, r]\) and asks you to count the number of inversion pairs in that subarray, i.e. the number of pairs \((i,j)\) such that

[ l \le i < j \le r \quad \text{and} \quad a_i > a_j, ]

Constraints:

• \(1\le n\le 10^5\)
• \(1\le m\le 5\times 10^5\)

You are required to answer all queries efficiently.

inputFormat

The first line contains two integers \(n\) and \(m\).
The second line contains \(n\) integers representing the sequence \(a_1, a_2, \dots, a_n\).
The following \(m\) lines each contain two integers \(l\) and \(r\) representing a query.

Note: The indices are 1-based.

outputFormat

For each query, output a single integer representing the number of inversion pairs in the subarray \([l, r]\). Output each answer on a new line.

sample

3 2
3 1 2
1 3
1 2

2
1