Problem Statement

You are given a sequence of length N consisting of integers: A=(A_1,\ldots,A_N).

Find the smallest non-negative integer not in (A_1,\ldots,A_N).

Constraints

• 1 \leq N \leq 2000
• 0 \leq A_i \leq 2000
• All values in input are integers.

Sample Input 1

8
0 3 2 6 2 1 0 0

Sample Output 1

4

The non-negative integers are 0,1,2,3,4,\ldots.
We have 0,1,2,3 in A, but not 4, so the answer is 4.

Sample Input 2

3
2000 2000 2000

Sample Output 2

0

Problem Statement

For a positive integer X, let \text{ctz}(X) be the (maximal) number of consecutive zeros at the end of the binary notation of X.
If the binary notation of X ends with a 1, then \text{ctz}(X)=0.

You are given a positive integer N. Print \text{ctz}(N).

Constraints

• 1\leq N\leq 10^9
• N is an integer.

Sample Input 1

2024

Sample Output 1

3

2024 is 11111101000 in binary, with three consecutive 0s from the end, so \text{ctz}(2024)=3.
Thus, print 3.

Sample Input 2

18

Sample Output 2

1

18 is 10010 in binary, so \text{ctz}(18)=1.
Note that we count the trailing zeros.

Sample Input 3

5

Sample Output 3

0

Problem Statement

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in their counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

• Rotate the turntable by one N-th of a counterclockwise turn. As a result, the dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i is happy if Dish i is in front of Person (i-1) \bmod N, Person i, or Person (i+1) \bmod N.
Find the maximum possible number of happy people.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 0 \leq p_i \leq N-1
• p_i \neq p_j if i \neq j.
• All values in input are integers.

Sample Input 1

4
1 2 0 3

Sample Output 1

4

The figure below shows the table after one operation.

Here, there are four happy people:

• Person 0 is happy because Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
• Person 1 is happy because Dish 1 is in front of Person 1\ (=1);
• Person 2 is happy because Dish 2 is in front of Person 2\ (=2);
• Person 3 is happy because Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

There cannot be five or more happy people, so the answer is 4.

Sample Input 2

3
0 1 2

Sample Output 2

3

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

5

Problem Statement

Your refrigerator has N kinds of ingredients. Let us call them ingredient 1, \dots, ingredient N. You have Q_i grams of ingredient i.

You can make two types of dishes. To make one serving of dish A, you need A_i grams of each ingredient i (1 \leq i \leq N). To make one serving of dish B, you need B_i grams of each ingredient i. You can only make an integer number of servings of each type of dish.

Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?

Constraints

• 1 \leq N \leq 10
• 1 \leq Q_i \leq 10^6
• 0 \leq A_i \leq 10^6
• There is an i such that A_i \geq 1.
• 0 \leq B_i \leq 10^6
• There is an i such that B_i \geq 1.
• All input values are integers.

Sample Input 1

2
800 300
100 100
200 10

Sample Output 1

5

This refrigerator has 800 grams of ingredient 1 and 300 grams of ingredient 2.

You can make one serving of dish A with 100 grams of ingredient 1 and 100 grams of ingredient 2, and one serving of dish B with 200 grams of ingredient 1 and 10 grams of ingredient 2.

To make two servings of dish A and three servings of dish B, you need 100 \times 2 + 200 \times 3 = 800 grams of ingredient 1, and 100 \times 2 + 10 \times 3 = 230 grams of ingredient 2, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is 5.

Sample Input 2

2
800 300
100 0
0 10

Sample Output 2

38

You can make 8 servings of dish A with 800 grams of ingredient 1, and 30 servings of dish B with 300 grams of ingredient 2, for a total of 38 servings.

Sample Input 3

2
800 300
801 300
800 301

Sample Output 3

0

You cannot make any dishes.

Sample Input 4

10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

Sample Output 4

222222

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.