[AdditionalFile5511.zip](file://AdditionalFile5511.zip?type=additional_file)

#5511. 「COI 2024」Koreografija

标签: 交互 | 时间限制: 8000 ms | 内存限制: 1024 MiB |

题目描述

译自 COI 2024 T2「Koreografija」

尤拉：特夫特科，昨天的演出怎么样？

特夫特科：太棒了。最精彩的部分是 $1000$ 名舞者从左到右排成一列，开始表演编舞。他们每个人的服装上都写着一个 $1$ 到 $1000$ 之间的数字，并且所有这些数字都各不相同。但我得承认，当我看到他们排成一列时，我并不喜欢他们的顺序。

尤拉：你这是什么意思？

特夫特科：我看到队伍中某个连续区间的舞者，并数了数其中有多少对舞者满足位置在前的舞者编号大于位置在后的舞者。我喜欢这种舞者对的数量是奇数的情况。

尤拉：哦，特夫特科，你得着眼于大局。这事我来处理。但告诉我，他们的编号顺序是怎样的？

特夫特科：嗯……我已经忘了。但我可以告诉你，对于任意一个连续的舞者区间，我喜不喜欢它。

尤拉：那就这样吧。我们别无选择，只能根据这些信息来尝试确定他们的编号了。

交互方式

这是一道交互式题目。你的程序需要与组织者制作的程序建立对话，以响应所提出的查询。

你的程序可以通过向标准输出写入内容来发送查询。每个查询应单独占一行，格式为 ? a b，其中 $a$ 和 $b$ 是满足 $1 \leq a \leq b \leq 1000$ 的正整数。数字 $a$ 和 $b$ 代表了所观察区间的舞者位置。

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

一旦你的程序重构出舞者服装上的数字，它应该向标准输出输出一行，内容为符号 !，后面跟着从左到右排列的所求数字序列。

之后，你的程序应再次刷新输出并终止执行。

样例

尽管在题目中舞者的数量总是 $1000$，为了便于说明，我们提供一个舞者数量为 $4$ 时的交互样例。

假设舞者服装上的数字顺序为 $2 \ 1 \ 4 \ 3$。

数据范围与提示

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

如果 $Q > 500000$，你的程序将得到 $0$ 分。

否则，你的程序得分将基于下表：