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 $N$ ($1\le N\le 5\cdot {10}^4$) integers ($0\le a_i\le {10}^7$), 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 $k$?" Because he is impatient, Max says you can only ask up to $5\cdot {10}^5$ questions.

Constraints

Subtask 1 [15%]

$0\le a_i\le {10}^5$

Subtask 2 [15%]

$1\le N\le {10}^4$

Subtask 3 [70%]

No additional constraints.

Interaction

The first line of input will be $N$, 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 $x$ 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 $[1,2,3,4]$, and its sum is $10$.