405190: GYM101821 E Guess Me If You Can

E. Guess Me If You Cantime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

This is an interactive problem.

Alice is a voice assistant recently introduced by Yandex. One of the directions to extend its functionality is to add different games that Alice can play with the users if they are bored. The game we are interested in has the following rules.

1. At the beginning Alice tells you some number n and thinks of some permutation of integers from 1 to n denoted as p₁, p₂, ..., p_n.
2. Your goal is to tell Alice where is the element equal to n located in the original permutation.
3. The only operation the other player has is to select some position i. After that Alice increases p_i by one and reports the number of distinct elements in the current array p₁, p₂, ..., p_n.

The game has different difficulty levels. The last level asks you to tell the position of n in original permutation in just 50·n questions. You are now working on your own voice assistant Boris and you want to teach it play this game, so you can put two phones next to each other as watch the battle.

Interaction

At the beginning Alice tells you the value of n (1 ≤ n ≤ 1000). Then, you can ask no more than 50·n questions of the form: "0 x", where 0 means that you are asking a question and x should be from 1 to n inclusive marking that Alice should increase p_x by one and report you the number of distinct elements in array p.

As soon as you are confident with the answer (or ran out of questions available) you must print: "1 x", where 1 means that you are reporting the answer and x is the answer itself, i.e. you claim that p_x = n was true at the beginning of the game. Your program must finish as soon as you print the answer. Otherwise you might get inappropriate judging verdict.

ExampleInput

5
1 5 2 4 3

Output

2

Note

The input sample section shows you a valid test case. First integer stands for the size of the permutation and then follows the permutation itself. One of the possible interaction scenarios looks as follows:

5
        0 1
4
        0 1
4
        0 3
3
        0 4
2
        1 2

Lines with two integers correspond to possible program outputs, while lines with one integer stand for the input your program should read.