Distinct Numbers

Limits 1s, 512 MB · Interactive

This is an Interactive Problem.

The judge has a secret array $A$ of size $n$.

You can ask the judge at most $10*n$ 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 $i, j(1 \leq i, j \leq n)$, the judge will reply with a character indicating the relation of the elements $A_i$ and $A_j$. There can be 3 types of responses,

1. < , if $A_i<A_j$

2. > , if $A_i > A_j$

3. = , if $A_i = A_j$

Input

Interaction Details:

The interaction starts with reading an integer $n(1 \leq n \leq 1000)$, 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 $A$. [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

Output

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.