B. Bogosort
time limit per test
6 s
memory limit per test
512 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is an array $$$[a_1, a_2, \ldots, a_N]$$$ initialized with a secret permutation of size $$$N = 100$$$.

Formally speaking, $$$\begin{cases}a_i \in \mathbb{N}, &\forall i = 1, 2, \ldots, N\\1 \leq a_i \leq N, &\forall i = 1, 2, \ldots, N\\ a_i \neq a_j, &\forall i \neq j \end{cases}$$$.

You are asked to sort it in ascending order within $$$50000$$$ operations. In each operation, you can perform any one of the following actions:

  • Pick a consecutive subarray of size at least $$$5$$$ and randomly shuffle it.
  • Query the $$$k$$$-th smallest value of $$$|a_i - i|$$$ for $$$i = 1, 2, \ldots, N$$$.
  • Claim that the array has been sorted.

Can you do it?

Input

Let me tell you a secret — there are $$$20$$$ test cases on the judge.

Interaction

The interaction begins without reading anything such as $$$N$$$. To perform an operation, please output a line:

  • # l r: Shuffle the interval $$$a[l..r]$$$. $$$l, r$$$ should satisfy $$$1 \leq l \leq r \leq 100$$$ and $$$r - l + 1 \geq 5$$$. After calling this operation, the judge shuffles $$$[a_l, a_{l + 1}, \ldots, a_r]$$$ randomly. That is, each possible $$$(r - l + 1)!$$$ permutations is equiprobably produced. After that, you should read a single integer $$$v$$$ written on a separate line. $$$v = 0$$$ if the shuffle action is successfully executed. Otherwise, you might have made an incorrect shuffle request; in this case, your program should terminate immediately to avoid undefined behavior.
  • ? k: Query the $$$k$$$-th smallest value of $$$|a_i - i|$$$ for $$$i = 1, 2, \ldots, N$$$. $$$k$$$ should satisfy $$$1 \leq k \leq N$$$. After that, you should read an integer $$$b$$$, the query result. If $$$b = -1$$$, you might have made an invalid query; in this case, your program should terminate immediately to avoid undefined behavior. Otherwise, $$$b$$$ is the value you asked for.
  • !: Claim that the array has been sorted. Once choosing this action, the judge takes a look on the current array to see if it is really sorted and gives you a verdict accrodingly. Your program should terminate immediately after calling this operation. Please note that this is also counted as an operation so it cannot be made on the $$$50001$$$-th move.
No matter what operation you have chosen, don't forget to output the end of line and flush the output. Otherwise, I don't know what is going to happen either. To flush the output, use:
  • fflush(stdout) in C;
  • fflush(stdout) or cout.flush() in C++;
  • stdout.flush() in Python;
Example
Input
0

0
Output
# 13 37

? 100

!
Note

In the first sample test case, you asked to shuffle the subarray $$$[a_{13}, a_{14}, \ldots, a_{37}]$$$. The judge accepted your request and did the operation successfully, outputting $$$0$$$ back to you.

Afterward, you wanted to determine if the array had been sorted. So, you output ? 100. Astonishingly, luck was on your side as the array had indeed become sorted after your previous action, resulting in the $$$100$$$-th smallest (or largest) value of all $$$|a_i - i|$$$ being equal to $$$0$$$. It's important to note that this outcome happens with an incredibly low probability, just 1 out of 933,262,154,439,441,526,816,992,388,562,667,004,907,159,682,643,816,214,685,929,638,952,175,999, 932,299,156,089,414,639,761,565,182,862,536,979,208,272,237,582,511,852,109,168,640,000,000,000, 000,000,000,000. Therefore, it's unlikely you'll be so fortunate next time.

After knowing that the array has been sorted, you output !, terminating your program.