Given a permutation of integers from $1$ to $n$ and $q$ queries, each query consisting of two integers $(l, r)$, count the number of inversions in the subarray $A_{l...r}$.
### Input
- The first line contains two positive integers $n, q$.
- The second line contains $n$ integers, a permutation of numbers from $1$ to $n$.
- The next $q$ lines each contain two integers $x, y$. The integers $l, r$ for this query are calculated as follows:
+ $l = (\text{lastans} + x) \mod n + 1$
+ $r = (\text{lastans} + y) \mod n + 1$.
If $l > r$, swap the values of $l, r$. $\text{lastans}$ is the answer from the previous query, and for the first query, $\text{lastans} = 0$ is assumed.
### Output
- For each query, print an integer as the answer.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le x, y \le 10^5$.
### Example
Input:
```
8 5
6 5 2 3 8 1 4 7
6 4
5 4
5 4
3 8
8 5
```
Output:
```
2
0
1
2
5
```