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.

  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score