B'This is an interactive problem. The jury has hidden a permutation ^ dagger p of length n . In one query, you can pick two integers l and r ( 1 <= l < r <= n ) by paying (r - l)^2 coins. In return, you will be given the number of inversions ^ ddagger in the subarray [p_l, p_{l + 1}, ldots p_r] . Find the index of the maximum element in p by spending at most 5 cdot n^2 coins. Note: the grader is not adaptive: the permutation is fixed before any queries are made. ^ dagger A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation ( 2 appears twice in the array), and [1,3,4] is also not a permutation ( n=3 but there is 4 in the array). ^ ddagger The number of inversions in an array is the number of pairs of indices (i,j) such that i < j and a_i > a_j . For example, the array [10,2,6,3] contains 4 inversions. The inversions are (1,2),(1,3),(1,4) , and (3,4) . Each test contains multiple test cases. The first line of input contains a single integer t ( 1 <= t <= 100 ) -- the number of test cases. The only line of each test case contains a single integer n ( 2 <= n <= 2000 ) -- the length of the hidden permutation p . It is guaranteed that the sum of n over all test cases does not exceed 2000 . The interaction for each test case begins by reading the integer n . To make a query, output "? l r" ( 1 <= l < r <= n ) without quotes. Afterwards, you should read one single integer -- the answer for your query. If you receive the integer -1 instead of an answer or a valid value of n , it means your program has made an invalid query, has exceed the limit of queries, or has given an incorrect answer on the previous te'...