{"raw_statement":[{"iden":"statement","content":"_This is an interactive problem. You have to use _flush_ operation right after printing each line. For example, in C++ you should use function _fflush(stdout)_, in Java — _System.out.flush()_, in Pascal — _flush(output)_ and in Python — _sys.stdout.flush()_._\n\nIn this problem, you need to find maximal and minimal elements of an array. What could be simpler?\n\nYou can imagine that the jury has an array, and initially you know the only number _n_ — array's length.\n\nArray's elements are numbered from 1 to _n_. You are allowed to compare two elements of the array by using their indices _i_ and _j_. There are three possible responses to this query: '_<_' (if _a__i_ is less than _a__j_), '_\\=_' (if _a__i_ is equal to _a__j_) and finally '_\\>_' (if _a__i_ is greater than _a__j_).\n\nIt's known that it's always possible to find both maximal and minimal elements of the array by using no more than comparisons, where ⌈ _x_⌉ is the result of rounding _x_ up.\n\nWrite the program that will find positions of the minimum and the maximum in the jury's array of length _n_, by using no more than _f_(_n_) comparisons."},{"iden":"interaction","content":"Each test for this problem will contain one or more arrays. You have to find positions of minimal and maximal elements for each of these arrays. The first line of the input contains integer _T_ (1 ≤ _T_ ≤ 1000) — number of arrays in the test.\n\nThus, at the beginning, you program should read number _T_, and then it should solve the problem for _T_ jury's arrays one by one.\n\nThen input for each array goes. Firstly, your program has to read the number _n_ (1 ≤ _n_ ≤ 50) — the length of the array. It will be provided in the next line of the input.\n\nFurther, your program can perform comparisons or report that the answer is found.\n\n*   To perform a comparison, you have to output string of the following pattern «_? i j_» (_i_ and _j_ must be integer numbers from 1 to _n_) — the indices of the elements to compare in the current query.\n*   To report the indices of minimal and maximal elements of the hidden array, your program have to output a line in the form «_! i j_» (_i_ and _j_ must be integer numbers from 1 to _n_), where _i_ is an index of the minimal element of array, and _j_ is an index of the maximal element of the array. If there are several possible answers to the problem, you can output any of them.\n\nThere are several possible responses for a comparison:\n\n*   '_<_' — if _a__i_ is less than _a__j_,\n*   '_\\=_' — if _a__i_ is equal to _a__j_,\n*   '_\\>_' — if _a__i_ is greater than _a__j_.\n\nFor an array of length _n_ your program can make at most comparisons. Note that the operation of reporting an answer («_! i j_» ) is not included into the value of _f_(_n_).\n\nAfter the answer is reported, your program has to solve the problem for the next array or it should terminate if all _T_ arrays are processed."},{"iden":"example","content":"Input\n\n2\n2\n \n>\n \n3\n \n=\n \n=\n \n\nOutput\n\n \n \n? 1 2\n \n! 2 1\n \n? 3 1\n \n? 2 1\n \n! 2 3"}],"translated_statement":[{"iden":"statement","content":"_This is an interactive problem. You have to use flush operation right after printing each line. For example, in C++ you should use function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush()._\n\nIn this problem, you need to find maximal and minimal elements of an array. What could be simpler?\n\nYou can imagine that the jury has an array, and initially you know the only number $n$ — array's length.\n\nArray's elements are numbered from $1$ to $n$. You are allowed to compare two elements of the array by using their indices $i$ and $j$. There are three possible responses to this query: '_<_' (if $a_i$ is less than $a_j$), '_=_' (if $a_i$ is equal to $a_j$) and finally '_>_' (if $a_i$ is greater than $a_j$).\n\nIt's known that it's always possible to find both maximal and minimal elements of the array by using no more than $\\lceil \\frac{3n}{2} \\rceil - 2$ comparisons, where $\\lceil x \\rceil$ is the result of rounding $x$ up.\n\nWrite the program that will find positions of the minimum and the maximum in the jury's array of length $n$, by using no more than $f(n) = \\lceil \\frac{3n}{2} \\rceil - 2$ comparisons.\n\nEach test for this problem will contain one or more arrays. You have to find positions of minimal and maximal elements for each of these arrays. The first line of the input contains integer $T$ ($1 ≤ T ≤ 1000$) — number of arrays in the test.\n\nThus, at the beginning, you program should read number $T$, and then it should solve the problem for $T$ jury's arrays one by one.\n\nThen input for each array goes. Firstly, your program has to read the number $n$ ($1 ≤ n ≤ 50$) — the length of the array. It will be provided in the next line of the input.\n\nFurther, your program can perform comparisons or report that the answer is found.\n\nThere are several possible responses for a comparison:\n\nFor an array of length $n$ your program can make at most $f(n)$ comparisons. Note that the operation of reporting an answer («_! i j_» ) is not included into the value of $f(n)$.\n\nAfter the answer is reported, your program has to solve the problem for the next array or it should terminate if all $T$ arrays are processed.\n\n"},{"iden":"interaction","content":"Each test for this problem will contain one or more arrays. You have to find positions of minimal and maximal elements for each of these arrays. The first line of the input contains integer $T$ ($1 ≤ T ≤ 1000$) — number of arrays in the test.Thus, at the beginning, you program should read number $T$, and then it should solve the problem for $T$ jury's arrays one by one.Then input for each array goes. Firstly, your program has to read the number $n$ ($1 ≤ n ≤ 50$) — the length of the array. It will be provided in the next line of the input.Further, your program can perform comparisons or report that the answer is found.  To perform a comparison, you have to output string of the following pattern «_? i j_» ($i$ and $j$ must be integer numbers from $1$ to $n$) — the indices of the elements to compare in the current query.  To report the indices of minimal and maximal elements of the hidden array, your program have to output a line in the form «_! i j_» ($i$ and $j$ must be integer numbers from $1$ to $n$), where $i$ is an index of the minimal element of array, and $j$ is an index of the maximal element of the array. If there are several possible answers to the problem, you can output any of them. There are several possible responses for a comparison:  '_<_' — if $a_i$ is less than $a_j$,  '_=_' — if $a_i$ is equal to $a_j$,  '_>_' — if $a_i$ is greater than $a_j$. For an array of length $n$ your program can make at most $f(n)$ comparisons. Note that the operation of reporting an answer («_! i j_» ) is not included into the value of $f(n)$.After the answer is reported, your program has to solve the problem for the next array or it should terminate if all $T$ arrays are processed."}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the length of the array.  \n- Let $ A_k = (a_{k,1}, a_{k,2}, \\dots, a_{k,n_k}) $ be an unknown sequence of comparable elements.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $: $ 1 \\le n_k \\le 50 $  \n3. The number of comparisons allowed for array $ k $ is at most $ \\left\\lceil \\frac{3n_k}{2} \\right\\rceil - 2 $  \n\n**Objective**  \nFor each array $ A_k $, determine indices $ i^*, j^* \\in \\{1, \\dots, n_k\\} $ such that:  \n- $ a_{k,i^*} = \\min\\{a_{k,1}, \\dots, a_{k,n_k}\\} $  \n- $ a_{k,j^*} = \\max\\{a_{k,1}, \\dots, a_{k,n_k}\\} $  \n\n**Interaction Protocol**  \n- Read $ n_k $.  \n- Perform comparisons by outputting \"? i j\" for $ i, j \\in \\{1, \\dots, n_k\\} $, and read response: \"<\", \"=\", or \">\".  \n- Report answer by outputting \"! i* j*\" (not counted toward comparison limit).  \n- Must flush output after each query or answer.  \n- Proceed to next test case until all $ T $ arrays are processed.","simple_statement":null,"has_page_source":false}