Given an permutation $P$ of $n$ integers and $q$ queries, each of the form $(l, r)$, count the number of inversions in the subarray $P[l...r]$.
An inversion in an array $A$ is a pair of indices $i < j$ and $A_i > A_j$.
### Input
- The first line contains 2 integers $n, q$.
- The second line contains $n$ integers $P_i$ which form a permutation.
- The next $q$ line, each line contains 2 integers $l, r$, a query.
### Output
- Print the answer for each query.
### Constraints
- $1 \le n,q \le 10^5$.
### Example
Input:
```
4 2
1 3 2 4
1 2
2 4
```
Output:
```
0
1
```
