Guess the Number

\textitThis is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java --- System.out.flush(), in Pascal --- flush(output), and in Python --- sys.stdout.flush().

In this problem, the jury has some number \(x\), and you have to guess it. The number \(x\) is always an integer from \(1\) to \(n\), where \(n\) is given to you at the beginning.

You can make queries to the testing system. Each query is a single integer from \(1\) to \(n\). Flush the output stream after printing each query. There are two different responses the testing program can provide:

• the string "<" (without quotes), if the jury's number is less than the integer in your query;
• the string ">=" (without quotes), if the jury's number is greater than or equal to the integer in your query.

When your program guesses the number \(x\), print the string "! x", where \(x\) is the answer, and terminate your program normally immediately after flushing the output stream.

Your program is allowed to make no more than \(25\) queries (not including printing the answer) to the testing system.

Input

Use standard input to read the responses to the queries.

The first line contains an integer \(n\) (\(1 \le n \le 10^6\)) --- maximum possible jury's number.

Following lines will contain responses to your queries --- strings "<" or ">=". The \(i\)-th line is a response to your \(i\)-th query. When your program guesses the number, print "! x", where \(x\) is the answer, and terminate your program.

The testing system will allow you to read the response to the query only after your program prints the query for the system and performs the flush operation.

Output

To make the queries, your program must use standard output.

Your program must print the queries --- integer numbers \(x_i\) (\(1 \le x_i \le n\)), one query per line (do not forget "end of line" after each \(x_i\)). After printing each line, your program must perform the flush operation.

Each of the values \(x_i\) means the query to the testing system. The response to the query will be given in the input file after you flush the output. In case your program guesses the number \(x\), print the string "! x", where \(x\) --- is the answer, and terminate your program.

Example

12 20