题目描述

这是一个交互式问题。

在这个问题中，评测机有一个数字 $k$，你需要猜出这个数字。数字 $k$ 是从 $1$ 到 $n$ 的一个整数，其中 $n$ 会在开始时给出。

你可以向评测系统发出查询。每个查询是一个从 $1$ 到 $n$ 的整数。在输出每次查询后，请执行 flush 操作。评测系统会返回以下两种可能的响应之一：

• 字符串 <（不含引号），表示评测系统的数字小于你的查询整数。
• 字符串 >=（不含引号），表示评测系统的数字大于或等于你的查询整数。

当你的程序猜测出数字 $k$ 时，打印 ! k（其中 $k$ 是答案），并立即正常终止程序，同时执行 flush 操作。

你的程序最多可以进行 $25$ 次查询（不包括输出答案）。

输入格式

交互

开始时，首先读取一个整数 $n$ ($1 \leq n \leq 10^6$)，表示 $k$ 的上界。接下来，你将开始猜测 $k$。

在猜测过程中，你可以进行最多 $25$ 次查询，每次查询的格式为：

• x，其中 $x$ 是一个满足 $1 \leq x \leq n$ 的整数。

对于每次查询，将返回以下响应之一：

• 如果 $k < x$，返回 <，表示 $k$ 小于你的查询整数。
• 如果 $x \leq k$，返回 >=，表示 $k$ 大于或等于你的查询整数。

当你确定了 $k$ 的值后，输出以下格式的答案：

• ! x，其中 $x$ 是你猜测 $k$ 的值 ($1 \leq x \leq n$)。

然后，程序应退出。

注意：

• 如果你的查询次数超过了 $25$ 或者提交了不正确的答案，评测机将会返回 -1 并视为答案错误，此时程序应立即终止，以避免不必要的后果。

每次输出查询或答案后，记得输出换行符并刷新输出缓冲区。否则，可能会导致程序被判定为运行时间超限。可以使用以下方法刷新缓冲区：

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

样例 #1

20

<

>=

>=

5

3

4

! 4

提示

对于 $25 \%$ 的数据，交互库并不是自适应性的，即 $k$ 是预先确定的。

对于 剩下的 $75 \%$ 的数据，交互库是自适应性的，也就是实际的交互库刚开始并没有一个确定的答案，而是会随着交互过程确定一个符合题意的值。