Jura：Tvrtko，昨天的演出怎么样？
Tvrtko：太棒了。最精彩的部分是 1000 名舞者从左到右排成一列开始表演编舞。他们每个人的服装上都写着一个 1 到 1000 之间的数字，且所有数字各不相同。但我不得不承认，当我看到他们排成一列时，我不喜欢他们的顺序。
Jura：你是什么意思？
Tvrtko：我观察了队列中一些连续的舞者区间，并计算了有多少对舞者满足：位置靠前的舞者身上的数字比位置靠后的舞者身上的数字大。当这样的数对数量为奇数时，我就会喜欢这个区间。
Jura：哦，Tvrtko，你要看大局。我会处理的。但告诉我，他们的数字顺序是怎样的？
Tvrtko：嗯……我已经忘了。但我可以告诉你对于每一个连续的舞者区间，我是否喜欢它。
Jura：好吧。我们别无选择，只能尝试根据这些信息来确定他们的数字。
交互
这是一个交互式任务。你的程序需要与组织者提供的程序建立对话，以响应所提出的查询。
你的程序可以通过向标准输出写入内容来发送查询。每个查询应打印在单独的一行中，格式为 ? a b，其中 $a$ 和 $b$ 是满足 $1 \le a \le b \le 1000$ 的正整数。数字 $a$ 和 $b$ 代表定义所观察区间的舞者位置。
在打印每个查询后，你的程序应刷新输出，并从标准输入读取对该查询的响应——一个来自集合 $\{0, 1\}$ 的数字，代表 Tvrtko 对给定区间的评价。数字 1 表示 Tvrtko 喜欢该区间，而 0 表示他不喜欢。
你的程序最多可以发送 500 000 次此类查询。
一旦你的程序重构出了舞者服装上的数字，它应该在标准输出的一行中打印符号 !，随后打印按从左到右顺序排列的数字序列。
之后，你的程序应再次刷新输出并终止执行。
子任务
设 $Q$ 为你的程序在所有测试用例中发送的最大查询次数。
如果 $Q > 500\,000$，你的程序将得 0 分。
否则，你的得分将根据下表计算：
| 数据范围 | 得分 |
|---|---|
| $40\,000 \le Q \le 500\,000$ | $30 + 70 \cdot \frac{1/Q - 1/500\,000}{1/40\,000 - 1/500\,000}$ |
| $Q \le 40\,000$ | $100$ |
样例
虽然在任务中舞者的数量始终为 1000，但为了说明起见，我们提供了一个舞者数量为 4 时的交互示例。
假设舞者服装上的数字顺序为 2 1 4 3。
输入格式 1
1 1 0 0 1 1
输出格式 1
? 1 2 ? 1 3 ? 1 4 ? 2 3 ? 2 4 ? 3 4 ! 2 1 4 3
说明
Tvrtko 对每个区间的评价如下：
- ? 1 2：Tvrtko 数出了一对。
- ? 1 3：Tvrtko 数出了一对。
- ? 1 4：Tvrtko 数出了两对。
- ? 2 3：Tvrtko 数出了零对。
- ? 2 4：Tvrtko 数出了一对。
- ? 3 4：Tvrtko 数出了一对。
- !：数字已被找到，按顺序打印。