Minimum and Maximum

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME80/hindi/MINMAXIN.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME80/bengali/MINMAXIN.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME80/mandarin/MINMAXIN.pdf), [Russian](http://www.codechef.com/download/translated/LTIME80/russian/MINMAXIN.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME80/vietnamese/MINMAXIN.pdf) as well. **This is an interactive problem.** There is a hidden sequence $A_1, A_2, \ldots, A_N$. You need to find indices of two smallest and two largest elements in it. Formally, you should find four integers $a$, $b$, $c$ and $d$ such that there is a permutation $P_1, P_2, \ldots, P_N$ of the integers $1$ through $N$ with the following properties:  for each $i$ ($1 \le i \lt N$), $A_{P_i} \le A_{P_{i+1}}$ holds  $P_1 = a$, $P_2 = b$, $P_{N1} = c$ and $P_N = d$ In order to find such indices, you may ask at most $Q$ questions. In each question, you should choose two integers $i$ and $j$ ($1 \le i, j \le N$); the grader compares the elements $A_i$ and $A_j$ and answers with $i$ if $A_i \le A_j$, or with $j$ if $A_i \gt A_j$. Note: The grader is adaptive, i.e. there is no initially fixed sequence $A$, but the grader chooses the answers to your questions in such a way that at any time, there is at least one sequence consistent with all the answers. The answer you choose should be correct for every sequence consistent with all the grader's answers. However, it is guaranteed that the grader is deterministic, i.e. its answers are uniquely determined by your questions. ### Interaction  First, you should read a line containing a single integer $T$ denoting the number of test cases. The description of interaction for $T$ test cases follows.  For each test case, first, you should read a line containing a single integer $N$. If $N = 2$, it means that your answer to the previous test case was incorrect and your program should terminate immediately.  Then, you may ask questions.  To ask a question, you should print a line containing three spaceseparated integers $1$, $i$ and $j$ ($1 \le i, j \le N$).  Then, you should read a line containing a single integer $x$.  If the question was invalid, then $x=2$. Otherwise, $x$ is the answer to the question, i.e. $i$ if $A_i \le A_j$ or $j$ otherwise.  When you have determined your answer, you should print a line containing five spaceseparated integers $2$, $a$, $b$, $c$ and $d$ ($1 \le a, b, c, d \le N$) that satisfy the conditions described above. If there are multiple possible solutions, you may find any one.  Whenever you read $2$, your program should terminate immediately to receive the Wrong Answer verdict. Otherwise, you may receive any verdict. **Don't forget to flush the output after printing each line!** ### Constraints  $1 \le T \le 5$  $4 \le N \le 1,000$ ### Subtasks **Subtask #1 (50 points):** $Q = 3N+20$ **Subtask #2 (50 points):** $Q = \lfloor \frac{3}{2}N \rfloor + 20$ ### Example ``` Grader You 1 4 1 1 2 1 1 2 1 2 1 1 3 3 1 1 4 4 1 3 4 4 2 4 3 1 2 ``` ### Explanation **Example case 1:** The hidden sequence is $A=[3, 3, 2, 1]$. Note that another possible solution is $a = 4$, $b = 3$, $c = 2$ and $d = 1$.Author:  farhod_farmon 
Editorial  https://discuss.codechef.com/problems/MINMAXIN 
Tags  easymedium, farhod_farmon, ltime80, observations, taran_1407 
Date Added:  2102019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 