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 \leq N \leq 5 \cdot 10^4~) integers (~0 \leq a_i \leq 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.
Subtask 1 (15%)
~0 \leq a_i \leq 10^5~
Subtask 2 (15%)
~1 \leq N \leq 10^4~
Subtask 3 (70%)
No further constraints.
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 the incorrect answer. In both cases you will receive a
>>> denotes your output. Do not print
4 >>> ? 1 4 >>> ? 2 3 >>> ? 3 2 >>> ? 4 1 >>> ! 10
The array was ~[1, 2, 3, 4]~, and its sum is ~10~.