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