There is a hidden array ~A~ of size ~N~, where ~A_i~ represents the colour of the ~i~th element. You are allowed at most ~M~ questions. In each question, you can query a range ~[l,r]~ and get the number of distinct colours in that range. Find an array ~B~ such that the colour scheme of ~B~ is equivalent to the colour scheme of ~A~. That is, for any pair ~1 \le i,j \le N~, either ~A[i]=A[j]~ and ~B[i]=B[j]~, or ~A[i] \neq A[j]~ and ~B[i] \neq B[j]~ must hold.

For example, ~A = [1,2,3,4,3,3,3,2,2,1]~ and ~B = [4,3,2,1,2,2,2,3,3,4]~ have an equivalent colour scheme.

Constraints

~1 \le N \le 5\,000~

~M = 120\,000~

Interaction

This is an interactive problem, where you and the judge exchange information back-and-forth to solve the problem.

At first, you should read in a line containing the integer ~N~.

You will then start the interaction by proceeding with your queries.

Each query should be formatted as ? l r followed by a \n character, with ~1 \le l \le r \le N~.

In response, the judge will return an integer ~x~ on its own line, whose value is the number of distinct integers in the range ~[l,r]~ of the hidden array ~A~.

If you believe you have the solution, you may output ! followed by a space-separated list of ~N~ integers ~B_1, B_2, \dots, B_N~, ~1 \le B_i \le N~, an array which has an equivalent colour scheme to the hidden array ~A~. You must terminate your program immediately after performing this operation. Note that this operation does not count towards the query limit of ~M~.

If at any point you attempt an invalid question (such as an invalid output format or an invalid range), or you exceed the query limit ~M~, the judge will respond with ~-1~. You should terminate your program immediately after receiving this feedback to receive a Wrong Answer verdict, or you may receive an arbitrary verdict. If the final list you output is incorrect, you will receive a Wrong Answer verdict. Otherwise, you will receive a verdict of Accepted for the corresponding test case.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Scoring

If you have received a verdict of Accepted, your score for the test case will be calculated as follows, where ~K~ is the number of queries that you used.

Your score for a batch is the minimum of the scores of all of the tests in the batch.

Sample Interaction

>>> denotes your output. Do not print this out.

Here, the hidden array ~A~ is ~[1,2,3]~. One of the possible valid arrays ~B~ is ~[3,2,1]~.

3
>>> ? 1 2
2
>>> ? 1 3
3
>>> ? 2 3
2
>>> ! 3 2 1

---