Sherlock and Subarray Queries
Watson gives to Sherlock an array of integers. He also gives him queries of the form . For each query, Sherlock has to find how many times the largest element of the subarray occurs in .
denotes the subarray .
Input Format
First line contains and . Next line contains integers denoting the array . Each of the next lines contain two space separated integers denoting and .
Output Format
For each query print the required answer in one line.
Constraints
Sample Input
5 3
3 1 3 2 1
1 3
2 5
1 5
Sample Output
2
1
2
Explanation
In subarray , the largest element is which occurs times.
In subarray , the largest element is which occurs times.
In subarray , the largest element is which occurs times.