CF1114E.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 \gt 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.

Interaction

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.

这是一个交互式问题！

等差数列（或称算术序列）是一组整数序列，满足任意元素与其前一元素之差（即 $x_i - x_{i - 1}$，其中 $i \ge 2$）为常数——该常数称为该序列的公差。

换言之，等差数列是形如 $x_i = x_1 + (i - 1) d$ 的序列，其中 $d$ 为公差。

现有一个长度为 $n$ 的秘密整数列表 $a_1, a_2, \ldots, a_n$。

保证所有元素 $a_1, a_2, \ldots, a_n$ 均在 $0$ 到 $10^9$（含端点）之间。

该列表具有特殊性质：若将其按升序排序，则得到一个公差为正（即 $d \gt 0$）的等差数列。例如，列表 $[14, 24, 9, 19]$ 满足该条件，排序后为 $[9, 14, 19, 24]$，可表示为 $x_n = 9 + 5 \cdot (n - 1)$。

此外，你被提供一台电量严重不足的设备，因此最多只能进行 60 次以下两类查询：

• 给定下标 $i$（$1 \le i \le n$），设备将返回 $a_i$ 的值；
• 给定数值 $x$（$0 \le x \le 10^9$），设备将返回 $1$ 当且仅当列表中存在严格大于 $x$ 的元素；否则返回 $0$。

你最多可使用该设备进行 60 次查询。请找出该等差数列的最小元素与公差，即定义中所述的 $x_1$ 和 $d$。注意：数组 $a$ 未排序。

交互流程

交互开始时，首先输入一个整数 $n$（$2 \le n \le 10^6$），表示整数列表的长度。

随后你可以执行以下两种类型的查询：

• "? i"（$1 \le i \le n$）—— 获取 $a_i$ 的值；
• "> x"（$0 \le x \le 10^9$）—— 查询是否存在大于 $x$ 的元素。

每次查询后，请读入一个整数结果 $r$：

• 对于第一类查询，$r$ 满足 $0 \le r \le 10^9$；
• 对于第二类查询，$r$ 为 $0$ 或 $1$；
• 若你执行了超过 60 次查询，或查询参数超出规定范围，则将收到 $r = -1$；
• 若你在收到 -1 后终止程序，将被判为“答案错误”（Wrong answer）；否则，由于你的程序会继续从已关闭的输入流中读取数据，可能得到任意判定结果。

当你确定最小元素 $x_1$ 和公差 $d$ 后，请输出：

• "! $x_1$ $d$"

并立即退出。该输出不计入 60 次查询限制。

每次输出查询（包括最终答案）后，请务必输出换行符并刷新输出缓冲区。否则你会收到“空闲超时”（Idleness limit exceeded）提示。刷新方法如下：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请查阅相应文档。

Hack（自定义测试用例）

用于 Hack 的输入格式如下：

第一行为一个整数 $n$（$2 \le n \le 10^6$）—— 列表长度；

第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）—— 列表元素。

此外，该列表排序后必须构成一个公差为正的等差数列。

Note that the example interaction contains extra empty lines so that it's easier to read. The real interaction doesn't contain any empty lines and you shouldn't print any extra empty lines as well.

The list in the example test is $[14, 24, 9, 19]$.

注意：示例交互中包含额外的空行，以便于阅读。实际交互中不包含任何空行，因此你也不应输出任何额外的空行。

示例测试中的列表为 $[14, 24, 9, 19]$。