Steven, the monkey, is baking banana bread today!
The recipe for banana bread calls for ~N~ ingredients numbered from ~1~ to ~N~. The recipe can be modelled as an array ~A~ of length ~N~, where ~A_i~ describes the amount for ingredient ~i~. Moreover, Steven's special banana bread recipe is a permutation of the first ~N~ positive integers!
Unfortunately, Steven lost the recipe and doesn't remember the ordering!
Fortunately, Steven had sent his recipe to his friend Tony for safekeeping. However, being a monkey, Tony obfuscated the recipe and tells Steven that he can only ask for the number of inversions present in some subarray of array ~A~ from ~l~ to ~r~ inclusive satisfying ~1 \le l < r \le N~. Due to how impatient Tony is, he informs Steven that he can only ask up to ~N~ questions. Help Steven recover the recipe so he can have dessert tonight!
A pair of indices ~i~ and ~j~ in the array ~A~ is considered an inversion if ~i < j~ and ~A[i] > A[j]~.
~1 \le N \le 3\,000~
Array ~A~ is a permutation of the first ~N~ positive integers.
This is an interactive problem.
You will start by reading in a single integer ~N~, the number of ingredients in the bread.
Note: The grader is NOT adaptive.
After reading ~N~ you can start interacting with the interactor.
To ask a query, you must output in the form
? l r to standard output. You will then read a single integer from standard input, which is the number of inversions in the contiguous subarray from ~l~ to ~r~.
To validate your final answer you must output
! followed by a space, then ~N~ space-separated numbers, which are the elements of the array ~A~. Your program should then terminate immediately.
The output must be flushed after every line is printed, including the last line.
In C/C++ you can use
cout << endl, in Java you can use
System.out.flush(), and in Python you can use
At any time if you ask an invalid query or exceed ~N~ queries, the interactor will print
-1. Once you read
-1, terminate your program immediately and you will receive a Wrong Answer verdict. Failure to terminate your program may result in an undefined result.
Sample Interaction 1
Note: Do not actually print out
>>> means that the interactor printed out the line, and
<<< means that you printed out the line.
>>> 5 <<< ? 3 4 >>> 0 <<< ? 1 5 >>> 5 <<< ? 2 4 >>> 0 <<< ! 3 2 4 5 1
Explanation for Sample Interaction 1
Our array is ~[3, 2, 4, 5, 1]~ and there are ~5~ inversions. The pairs of indices that form inversions are ~(1, 2), (1, 5), (2, 5), (3, 5), (4, 5)~.
Sample Interaction 2
>>> 3 <<< ? 1 2 >>> 0 <<< ! 1 2 3