23435번 - Cloud computing 다국어인터랙티브

Cloud computations are gaining popularity as a powerful and versatile tool. However, they are seriously flawed: processing your data on a remote computer puts your information safety at risk.

Vanya works in an Organization which implemented cloud computing for calculating order statistics of arrays. An order statistic of an array for a specific $k$ is the value of the element, which is $k$th in the array, if the array is sorted.

However, the array which requires order statistics is extremely classified. The only thing known about it is that all its elements are different. With this in mind, Vanya came up with the following scheme: the array is stored on the Organization's server, and the cloud server performing the order statistics calculations can access the Organization's server to get the results of the comparison of two elements of the array. In this manner, the cloud server can define the position of the $k$th order statistic, and the classified array is never revealed to the cloud server. This produces another problem: the number of requests from the cloud server to the Organization's server should not be exceedingly large.

In particular, Vanya decided to limit the calculations of the second order statistics to no more than $N + 20$ requests, where $N$ is the size of the array. Help Vanya implement an algorithm of finding the second largest element of the classified array, such that it complies to this limitation.

This is an interactive problem. Instead of file input-output, you will be working with a special program --- the interactor, using the standard input-output streams. When your program starts, it feeds the integer $N$ into the standart input stream --- the size of the array(2 $\le$ $N$ $\le$ $10^5$).

Next, your program must send requests to the standard output stream.

Each request must consist of a single line with a question mark ("?") followed by two different, space-separated numbers $I$ and $J$ --- the indices of those elements of the array that must be compared (0 $\le$ $I$, $J$ < $N$). In return, you get a string containing the "less" symbol ("<"), if the $I$th element of the secret array is smaller than the $J$th one, or the "more" symbol (">"), if the $J$th element of the secret array is smaller than the $I$th one.

When your program defines the position of its second order statistic in the classified array, it must print a line with that position following an exclamation mark ("!") and separated by a space symbol.

Make sure that you arer printing the line break symbol and clearing the output stream buffer (the flush command of the language) after every printed line. Otherwise the solution can receive the Timeout verdict.

Pay attention: interactor could alter the contents of the classified array in runtime if all the previously given answers stay true.