There is a hidden array of size , where represents the colour of the th element. You are allowed at most questions. In each question, you can query a range and get the number of distinct colours in that range. Find an array such that the colour scheme of is equivalent to the colour scheme of . That is, for any pair , either and , or and must hold.

For example, and have an equivalent colour scheme.

#### Constraints

#### 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 .

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 .

In response, the judge will return an integer on its own line, whose value is the number of distinct integers in the range of the hidden array .

If you believe you have the solution, you may output `!`

followed by a space-separated list of integers , , an array which has an equivalent colour scheme to the hidden array . You must terminate your program immediately after performing this operation. Note that this operation does **not** count towards the query limit of .

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 , the judge will respond with . 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 is the number of queries that you used.

Score | |
---|---|

points | |

points | |

points |

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 is . One of the possible valid arrays is .

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

## Comments