Inversion Count Queries

Given a sequence \(a\) of length \(n\).

There are \(m\) queries. Each query provides an interval \([l, r]\). For each query, count the number of inversion pairs \(\{(a_i,a_j) : l \le i a_j\}\) within that interval.

inputFormat

The input begins with two integers \(n\) and \(m\) separated by a space.

The next line contains \(n\) integers representing the array \(a\).

Each of the following \(m\) lines contains two integers \(l\) and \(r\), representing a query interval in 1-indexed format.

outputFormat

For each query, output a single line containing the inversion count in the specified subarray.

sample

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

2
1
3