# Practice on Toph

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

## Smallest Subarray

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<=10^5)**. The next line contains N integers the value of **A1, A2, A3, …, An (1 <= Ai <= 10^9)**. 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.

#### Samples

Input | Output |
---|---|

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.

Login to submit