It's lunchtime, and as usual, Andy is trying to buy drinks from the vending machine.
The vending machine wants to play a game with Andy.
The vending machine hides a -indexed array consisting of distinct integers from to . The vending machine defines the rank of a number as the number of numbers smaller than it in the array.
Andy will try to find the index of the numbers in array with rank , where is the largest number such that . In other words, find the indices of the numbers .
Andy struggles to get the answer and asks you to help out.
You can perform two types of queries:
Query 1: You provide the vending machine with two indices and , and the vending machine will compare the two numbers at those indices and output
1 if and
0 if . This query costs dollar.
Query 2: You provide the vending machine with an array of size which consists of distinct integers for all indices in and an integer . The machine will return an integer , which is the index of the ranked number within the array . is given as the index in the original -indexed array . This query costs dollars.
You need to get the answer by spending at most dollars.
For all subtasks:
All integers in are distinct.
Subtask 1 [10%]
Subtask 2 [90%]
No additional constraints.
This is an interactive problem. The first line of input contains an integer .
To ask query 1, you output the following:
To ask query 2, you output the following:
If you believe you found the answer, output followed by , where is the largest integer such that , followed by integers (followed by
\n character), representing the numbers with rank , respectively. You must terminate your program immediately after performing this operation. Note that this operation does not cost anything.
The grader is not adaptive.
If at any point your query is malformed or your cost exceeds dollars, your program will receive
-1, and the interactor will terminate. Upon receiving
-1, your program should terminate to avoid an undefined verdict.
Please note: the judge requires your whitespace to match exactly.
If you attempt an invalid operation (such as an invalid output format), you will receive a
Presentation Error verdict.
If you exceed a cost of dollars, query incorrectly, or output incorrect final result, you will receive a
Wrong Answer verdict.
Please note that you may need to flush
stdout after each operation, or interaction may halt. In C++, this can be done with
cout << flush (depending on whether you use
cout). In Java, this can be done with
System.out.flush(). In Python, you can use
>>> denotes your output. Do not print this out.
The array is .
7 >>> ? 1 3 1 >>> ? 5 6 0 >>> $ 7 0 1 2 3 4 5 6 0 5 >>> $ 4 0 2 4 6 3 2 >>> ! 2 6 4 3
Explanation for Sample
For the first query, , so it prints .
For the second query, , so it prints .
For the third query, the whole array is being asked, and at index is ranked . Thus, it prints .
For the fourth query, the array is being asked. The number with a rank of is , with an index of in array . Thus, it prints .
For the final operation, . The number has index . The number has index . The number has index .
The total cost of this interaction is dollars, which is less than dollars.