Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Answer the Queries

By amirul_islam · Limits 1s, 512 MB

Given an array of N elements, indexed from 0 to N-1. Now you are given some queries in the form [L, R] inclusive. Your task is to find the number of occurence of the highest value from L to R.

Let’s say, an array A = {1001, 3, 5, 5, 99}, and L = 2, R = 3. So, here the highest value from index 2 to 3 is 5 and the number of occurence of 5 is exactly 2. So, you have to print 2.

Input

Input begins with an integer T, denoting the number of test cases.

Each case starts with two integers N and Q. The next line contains N space separated integers forming the array A.

The next Q lines will contain the queries which is in the form L to R.

Constrains:
* 1 ≤ T ≤ 20
* 1 ≤ N, Q ≤ 104
* -2x105 < A[i] < 2x105
* 0 ≤ L ≤ R < N

Output

For each test case, print the case number in a single line. Then for each query you have to print the number of occurrence of the maximum number between index L to R.

Sample

InputOutput
1
5 3
1001 3 5 5 99
1 2
2 3
0 4
Case 1:
1
2
1


Discussion
Statistics

63% Solution Ratio

arknaveEarliest, 1M ago

mahdi.hasnatFastest, 0.1s

PrimeXLightest, 655 kB

Statue_OfBasharShortest, 1058B

Submit

Login to submit