Online Inversion Queries

You are given a permutation of length \(n\) and \(m\) queries. Initially, you are given a permutation \(P\) containing \(n\) distinct integers. Each query is performed online and provided as two integers \(x\) and \(y\). For each query, let \(\text{lastans}\) be the answer of the previous query (initially \(0\)). Compute:

\( l = ((x + \text{lastans}) \bmod n) + 1 \) and \( r = ((y + \text{lastans}) \bmod n) + 1 \). If \(l > r\), swap \(l\) and \(r\).

You need to count the number of inversion pairs \((i, j)\) in the subarray \(P[l...r]\) such that \(l \le i P[j]\).

inputFormat

The first line contains two integers \(n\) and \(m\). The second line contains \(n\) integers representing the permutation \(P\). Each of the next \(m\) lines contains two integers \(x\) and \(y\), representing the query parameters.

outputFormat

For each query, output a single integer denoting the number of inversion pairs in the subarray.

sample

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

0
1
1