At school, Max is learning how to add numbers together! He finds the task of adding numbers too easy, so he gives you the following problem: sum an array of () integers (), *without looking at the array*. Instead, you're only allowed to ask the following question: "How many numbers in the array are greater than or equal to ?" Because he is impatient, Max says you can only ask up to questions.

#### Constraints

##### Subtask 1 [15%]

##### Subtask 2 [15%]

##### Subtask 3 [70%]

No additional constraints.

#### Interaction

The first line of input will be , the number of items in the array.

To ask questions, output `? k`

, followed by a newline. The next line of input will be the answer to your question.

To submit your answer, output `! x`

(followed by a newline), where is the sum of all the numbers.

If your output is ever invalid, undefined behavior will be invoked.

**Please note that the grader for this problem does not differentiate between asking too many queries or giving an incorrect answer. In both cases, you will receive a WA verdict.**

#### Sample Interaction

`>>>`

denotes your output. Do not print `>>>`

out.

```
4
>>> ? 1
4
>>> ? 2
3
>>> ? 3
2
>>> ? 4
1
>>> ! 10
```

#### Sample Explanation

The array was , and its sum is .

## Comments