题目背景

题目来源：https://hsin.hr/hio2024/。翻译来自 文心一言。如果有更好的翻译请在讨论区提供。

题目描述

Jura：Tvrtko，昨天的演出怎么样？
Tvrtko：非常棒。最精彩的部分是当 $1000$ 名舞者从左到右排列并开始表演时，那个编舞。他们每个人的服装上都写有一个 $1$ 到 $1000$ 之间的数字，并且这些数字都是不同的。但我不得不说，当我看到他们排成一行时，我不喜欢他们的顺序。
Jura：你是什么意思？
Tvrtko：我在队伍中看到了一些连续的舞者间隔，并计算了有多少对舞者是这样的：较低位置的舞者编号高于较高位置的舞者编号。我喜欢这样的对数是奇数的情况。
Jura：哦，Tvrtko，你得看大局。我会处理的。但告诉我，他们的编号顺序是怎样的？
Tvrtko：嗯……我已经忘了。但我可以告诉你对于每个连续的舞者间隔，我是否喜欢。
Jura：就这样吧。我们别无选择，只能尝试根据这个来确定他们的编号。

输入格式

这是一个交互任务。你的程序需要与组织者提供的程序建立对话，以响应所提出的问题。

你的程序可以通过向标准输出写入来发送查询。每个查询应单独打印在一行上，并应采用 ? a b 的形式，其中 $a$ 和 $b$ 是满足 $1 \leq a \leq b \leq 1000$ 的正整数。数字 $a$ 和 $b$ 表示所观察区间的舞者位置。

在输出每个查询后，你的程序应刷新输出，并从标准输入读取对查询的响应——一个在集合 $\{0,1\}$ 的数字，表示 Tvrtko 对该区间的看法：数字 $1$ 表示 Tvrtko 喜欢那个区间，而 $0$ 表示他不喜欢。你的程序最多可以发送 $500000$ 个这样的查询。

一旦你的程序计算出了舞者服装上的数字，它应在单独的一行上向标准输出打印符号 ! 后跟从左到右出现的请求的数字序列。之后，你的程序应再次刷新输出并终止执行。

提示

【解释说明】

尽管在任务中舞者的数量总是为 $1000$，但为了说明目的，我们提供了一个当舞者数量为 $4$ 时的交互示例。

假设：舞者服装上的数字按顺序为 $2,1,4,3$。下面是一种可能的查询方案：

• 查询 ? 1 2，Tvrtko 数到了一对。
• 查询 ? 1 3，Tvrtko 数到了一对。
• 查询 ? 1 4，Tvrtko 数到了两对。
• 查询 ? 2 3，Tvrtko 没有数到任何一对。
• 查询 ? 2 4，Tvrtko 数到了一对。
• 查询 ? 3 4，Tvrtko 数到了一对。
• 使用 ! 2 1 4 3 输出答案。

【评分细则】

设 $Q$ 为你的程序在所有测试用例中发送的最大查询数。

如果 $Q > 5\times 10^5$，你的程序将得 $0$ 分。

否则，你的程序将获得的分数基于以下表格：