A12446 | Arithmetic Progression

This is an interactive problem!

An arithmetic progression or arithmetic sequence is a sequence of integers such that the subtraction of element with its previous element ( $x_i - x_{i - 1}$ , where $i \ge 2$ ) is constant — such difference is called a common difference of the sequence.

That is, an arithmetic progression is a sequence of form $x_i = x_1 + (i - 1) d$ , where $d$ is a common difference of the sequence.

There is a secret list of $n$ integers $a_1, a_2, \ldots, a_n$ .

It is guaranteed that all elements $a_1, a_2, \ldots, a_n$ are between $0$ and $10^9$ , inclusive.

This list is special: if sorted in increasing order, it will form an arithmetic progression with positive common difference ( $d > 0$ ). For example, the list $[14, 24, 9, 19]$ satisfies this requirement, after sorting it makes a list $[9, 14, 19, 24]$ , which can be produced as $x_n = 9 + 5 \cdot (n - 1)$ .

Also you are also given a device, which has a quite discharged battery, thus you can only use it to perform at most $60$ queries of following two types:

- Given a value $i$ ( $1 \le i \le n$ ), the device will show the value of the $a_i$ .
- Given a value $x$ ( $0 \le x \le 10^9$ ), the device will return $1$ if an element with a value strictly greater than $x$ exists, and it will return $0$ otherwise.

Your can use this special device for at most $60$ queries. Could you please find out the smallest element and the common difference of the sequence? That is, values $x_1$ and $d$ in the definition of the arithmetic progression. Note that the array $a$ is not sorted.

无

The interaction starts with a single integer $n$ ( $2 \le n \le 10^6$ ), the size of the list of integers.

Then you can make queries of two types:

- "? i" ( $1 \le i \le n$ ) — to get the value of $a_i$ .
- "> x" ( $0 \le x \le 10^9$ ) — to check whether there exists an element greater than $x$

After the query read its result $r$ as an integer.

- For the first query type, the $r$ satisfies $0 \le r \le 10^9$ .
- For the second query type, the $r$ is either $0$ or $1$ .
- In case you make more than $60$ queries or violated the number range in the queries, you will get a $r = -1$ .
- If you terminate after receiving the -1, you will get the "Wrong answer" verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

When you find out what the smallest element $x_1$ and common difference $d$ , print

- "! $x_1$ $d$ "

And quit after that. This query is not counted towards the $60$ queries limit.

After printing any query do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Hacks

For hack, use the following format:

The first line should contain an integer $n$ ( $2 \le n \le 10^6$ ) — the list's size.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 10^9$ ) — the elements of the list.

Also, after the sorting the list must form an arithmetic progression with positive common difference.