This is an Interactive Problem.
The judge has a secret array of size .
You can ask the judge at most queries, and after that, you have to figure out the number of distinct elements in the array.
Query: To do a query you will give the judge two integers , the judge will reply with a character indicating the relation of the elements and . There can be 3 types of responses,
< , if
> , if
= , if
Interaction Details:
The interaction starts with reading an integer , the size of the secret array.
After that to do a query print “? i j” in a line and flush the output stream.
Read a character in a line, the response from the judge.
When you are ready to answer, print “! x” in a line. Here x is the number of distinct elements in . [Note: This does not count as one of the queries.]
After that flush the output stream and finish!
To flush the output stream, you may use:
fflush(stdout) in C/C++
stdout.flush() in Python
A sample interaction is given below if the secret array was [1, 2, 1, 3]
>> 4
<< ? 1 4
>> <
<< ? 1 3
>> =
<< ! 3
Another one if the secret array was [1, 1, 1, 2, 1, 1]
>> 6
<< ? 1 2
>> =
<< ? 3 4
>> <
<< ? 5 6
>> =
<< ! 2
Here '>>' indicates what your program reads and '<<' indicates what your program writes. These symbols are here to make it easy to understand. You do not have to print such symbols from your program.