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 Ai>Aj.
### Input
- The first line contains 2 integers n,q.
- The second line contains n integers Pi 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≤n,q≤105.
### Example
Input:
4213241224
Output:
01
