Problem Statement

We will call a sequence of length N where each of 1,2,\dots,N occurs once as a permutation of length N.
Given a permutation of length N, P = (p_1, p_2,\dots,p_N), print a permutation of length N, Q = (q_1,\dots,q_N), that satisfies the following condition.

• For every i (1 \leq i \leq N), the p_i-th element of Q is i.

It can be proved that there exists a unique Q that satisfies the condition.

Constraints

• 1 \leq N \leq 2 \times 10^5
• (p_1,p_2,\dots,p_N) is a permutation of length N (defined in Problem Statement).
• All values in input are integers.

Sample Input 1

3
2 3 1

Sample Output 1

3 1 2

The permutation Q=(3,1,2) satisfies the condition, as follows.

• For i = 1, we have p_i = 2, q_2 = 1.
• For i = 2, we have p_i = 3, q_3 = 2.
• For i = 3, we have p_i = 1, q_1 = 3.

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3

If p_i = i for every i (1 \leq i \leq N), we will have P = Q.

Sample Input 3

5
5 3 2 4 1

Sample Output 3

5 3 2 4 1

Problem Statement

Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

• Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
1 2 4 6 7 271

Sample Output 1

4

Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

5

Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:

• Sell two books of Volume 1 and buy a book of Volume 2 instead.
• Sell two books of Volume 1 and buy a book of Volume 3 instead.
• Sell two books of Volume 1 and buy a book of Volume 4 instead.
• Sell two books of Volume 1 and buy a book of Volume 5 instead.

Sample Input 3

1
5

Sample Output 3

0

Takahashi cannot read Volume 1.

Problem Statement

This is an interactive task, where your program and the judge interact via Standard Input and Output.

The judge has a string of length N consisting of 0 and 1: S = S_1S_2\ldots S_N. Here, S_1 = 0 and S_N = 1.

You are given the length N of S, but not the contents of S. Instead, you can ask the judge at most 20 questions as follows.

• Choose an integer i such that 1 \leq i \leq N and ask the value of S_i.

Print an integer p such that 1 \leq p \leq N-1 and S_p \neq S_{p+1}.
It can be shown that such p always exists under the settings of this problem.

Constraints

• 2 \leq N \leq 2 \times 10^5

Input and Output

First, receive the length N of the string S from Standard Input:

N

Then, you get to ask the judge at most 20 questions as described in the problem statement.

Print each question to Standard Output in the following format, where i is an integer satisfying 1 \leq i \leq N:

? i

In response to this, the value of S_i will be given from Standard Input in the following format:

S_i

Here, S_i is 0 or 1.

When you find an integer p satisfying the condition in the problem statement, print it in the following format, and immediately quit the program:

! p

If multiple solutions exist, you may print any of them.

Notes

• Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.
• If there is malformed output during the interaction or your program quits prematurely, the verdict will be indeterminate.
• After printing the answer, immediately quit the program. Otherwise, the verdict will be indeterminate.
• The string S will be fixed at the start of the interaction and will not be changed according to your questions or other factors.

Sample Input and Output

In the following interaction, N = 7 and S = 0010011.

For the presented p = 5, we have 1 \leq p \leq N-1 and S_p \neq S_{p+1}. Thus, if the program immediately quits here, this case will be judged as correctly solved.

Problem Statement

We have a sequence A=(A_1,A_2,\dots,A_N) of length N. Initially, all the terms are 0.
Using an integer K given in the input, we define a function f(A) as follows:

• Let B be the sequence obtained by sorting A in descending order (so that it becomes monotonically non-increasing).
• Then, let f(A)=B_1 + B_2 + \dots + B_K.

We consider applying Q updates on this sequence.
Apply the following operation on the sequence A for i=1,2,\dots,Q in this order, and print the value f(A) at that point after each update.

• Change A_{X_i} to Y_i.

Constraints

• All input values are integers.
• 1 \le K \le N \le 5 \times 10^5
• 1 \le Q \le 5 \times 10^5
• 1 \le X_i \le N
• 0 \le Y_i \le 10^9

Sample Input 1

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

Sample Output 1

5
6
8
8
15
13
13
11
1
0

In this input, N=4 and K=2. Q=10 updates are applied.

• The 1-st update makes A=(5, 0,0,0). Now, f(A)=5.
• The 2-nd update makes A=(5, 1,0,0). Now, f(A)=6.
• The 3-rd update makes A=(5, 1,3,0). Now, f(A)=8.
• The 4-th update makes A=(5, 1,3,2). Now, f(A)=8.
• The 5-th update makes A=(5,10,3,2). Now, f(A)=15.
• The 6-th update makes A=(0,10,3,2). Now, f(A)=13.
• The 7-th update makes A=(0,10,3,0). Now, f(A)=13.
• The 8-th update makes A=(0,10,1,0). Now, f(A)=11.
• The 9-th update makes A=(0, 0,1,0). Now, f(A)=1.
• The 10-th update makes A=(0, 0,0,0). Now, f(A)=0.

Problem Statement

On a blackboard, there are N sets S_1,S_2,\dots,S_N consisting of integers between 1 and M. Here, S_i = \lbrace S_{i,1},S_{i,2},\dots,S_{i,A_i} \rbrace.

You may perform the following operation any number of times (possibly zero):

• choose two sets X and Y with at least one common element. Erase them from the blackboard, and write X\cup Y on the blackboard instead.

Here, X\cup Y denotes the set consisting of the elements contained in at least one of X and Y.

Determine if one can obtain a set containing both 1 and M. If it is possible, find the minimum number of operations required to obtain it.

Constraints

• 1 \le N \le 2 \times 10^5
• 2 \le M \le 2 \times 10^5
• 1 \le \sum_{i=1}^{N} A_i \le 5 \times 10^5
• 1 \le S_{i,j} \le M(1 \le i \le N,1 \le j \le A_i)
• S_{i,j} \neq S_{i,k}(1 \le j < k \le A_i)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

2

First, choose and remove \lbrace 1,2 \rbrace and \lbrace 2,3 \rbrace to obtain \lbrace 1,2,3 \rbrace.

Then, choose and remove \lbrace 1,2,3 \rbrace and \lbrace 3,4,5 \rbrace to obtain \lbrace 1,2,3,4,5 \rbrace.

Thus, one can obtain a set containing both 1 and M with two operations. Since one cannot achieve the objective by performing the operation only once, the answer is 2.

Sample Input 2

1 2
2
1 2

Sample Output 2

0

S_1 already contains both 1 and M, so the minimum number of operations required is 0.

Sample Input 3

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

Sample Output 3

-1

Sample Input 4

4 8
3
1 3 5
2
1 2
3
2 4 7
4
4 6 7 8

Sample Output 4

2