Consider an array of integers, . Let and be the respective maximum and minimum values in the inclusive range between index and .
Given , perform queries where each query consists of two integers, and . For each query, find and print the number of pairs that satisfy the following:
- .
Input Format
The first line contains two space-separated integers describing the respective values of (the size of array ) and (the number of queries).
The second line contains space-separated integers describing the respective values of .
Each line of the subsequent lines contains two space-separated integers describing the respective values of and for the query.
Constraints
- for
Output Format
Print lines where each line is the number of possible pairs for the query.
Sample Input 0
4 3
1 2 1 4
1 1
2 2
2 3
Sample Output 0
3
0
3
Explanation 0
The diagram below breaks down the possible pairs for each query on :
As you can see, the first query has pairs, the second has pairs, and the third has pairs.