Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution H - An Interesting Game

H. An Interesting Game

Score: 1

CPU: 8s
Memory: 1200MB

Let’s play a game. You might like it.

You are given an array of N integers. All the numbers are distinct and between [1...N].

The rule of the game is simple. You will be given two integers, let’s call them L, R (1 ≤ L ≤ R ≤ N). You need to find out the length of the largest contiguous sub-array of the given permutation in which every value is between L and R inclusive. You will be given many queries like this for the given array. You win if you can answer all the queries perfectly and in time. Can you win this game?

Input

The first line has an integer T (The number of test scenarios, 1≤ T ≤ 5). Then T test cases follow. Each test had two integers at the first line N, Q (1 ≤ N, Q ≤ 100000). Then the next line contains a permutation of positive integers between 1...N. The next Q lines contain pairs of integers: L and R.

Output

For each test case print the case number at the first line as “Case T:”, where T is the test case number. Then for each test case, print Qlines, each line should contain the length of the largest sub-array of the array which contains all the values only from [L, R] (inclusive). See the sample input/output for more details.

Sample

Input	Output
1 6 3 1 5 2 3 6 4 1 5 1 4 3 4	Case 1: 4 2 1

*Warning: Large I/O file, user faster input output functions.