Limits 2s, 512 MB

You are given an array A of N integers A1, A2, A3, ..., AN . If we select two indices (1 ≤ i ≤ j ≤ N) from the array then there are (j-i+1) subarrays in total which starts in any index between i (inclusive) and j (inclusive) and ends in the last index of the array that is N.

Now you are given Q queries. In each query there are 2 integers.

For each query you have to answer the following question: What is the position of the smallest subarray which starts in any position between a (inclusive) and b (inclusive) and ends in the last index of the of the array N.

N.B: An array of m integers F1, F2, F3, ..., Fm is smaller than another array of n integers S1, S2, S3, ..., Sn if and only if there exists an index i such that i <= m and i ≤ n and F1 = S1, F2 = S2, F3 = S3, ..., Fi-1 = Si-1 and Fi < Si or F1 = S1, F2 = S2, F3 = S3, ..., Fm = Sm and m < n.

Input

The first line contains the number of testcases T (1 ≤ T ≤10).

Then in every test case the first line contains two space separated integers N (1 ≤ N ≤ 50000) and Q (1 ≤ Q ≤ 105). The next line contains N integers the value of A1, A2, A3, ..., An (1 ≤ Ai ≤ 109). Then Q lines follow. Each line contains 2 space separated integers a and b (1 ≤ a ≤ b ≤ N) the value of which have been described in the statement.

Output

For each case print the case number in the format “Case X:” where ‘X’ should be replaced with case number and the output of each query in each new line. Check the sample I/O for better understanding.

Sample

InputOutput
2

6 3
5 8 3 2 5 1
1 6
1 5
3 5

4 2
1 3 2 1
1 2
2 4
Case 1:
6
4
4
Case 2:
1
4

This problem was authored for Inter Department Programming Contest 2016 at Jahangirnagar University and is being hosted on Toph per author's request.

Submit

Login to submit.

Statistics

74% Solution Ratio
Bishal_GEarliest, Feb '16
mumith_fahim99Fastest, 0.1s
OptimusV2Lightest, 2.0 MB
mumith_fahim99Shortest, 1561B
Toph uses cookies. By continuing you agree to our Cookie Policy.