背景

Yet Another Interactive Problem About Permutation

题目描述

这是一道交互题。

评测系统有一个隐藏的 $1 \sim n$ 的排列 $p$。

每次你可以询问两个整数 $l, r$ 使得 $1 \le l \le r \le n$。评测系统会执行以下步骤：

1. 将 $p$ 的子段 $p[l, \ldots, r]$ 循环移位一次。
2. 评测系统会返回一个长度为 $n$ 的 $\texttt{01}$ 序列 $s$，其中 $s_i = 1$ 当且仅当 当前 $p_i = i$。

在本题中，对一个非空序列循环移位一次定义为：将序列首个元素的值插入到序列末尾，并删除序列首个元素。

你的目标是通过一系列操作，使得最终的排列 $p$ 升序排列，即对于所有 $i \in [1, n]$，有 $p_i = i$。

交互方式

你的程序需要通过标准输入输出与评测系统交互。

首先，程序应读入一个数 $n$，表示隐藏的排列的长度。接下来，程序应开始询问，每次询问格式为：

? l r

其中 $l, r$ 是两个正整数，满足 $1 \le l \le r \le n$。每次询问后，评测系统会返回一个长度为 $n$ 的 $\texttt{01}$ 串，你的程序应从标准输入读取该返回值。

当你认为 $p$ 已经升序排列时，应报告，格式为：

!

输出答案后，你的程序应立即结束。

你最多可以进行 不超过 $2026$ 次询问。如果询问次数超过限制，或者答案错误，或者格式不符合要求，评测系统将判定为错误答案。

注意：每次输出后必须刷新缓冲区，例如 C++ 中使用 cout << endl 或 fflush(stdout)，Python 中使用 print(..., flush=True)。

你可以忽略交互库的运行时间。

4

1001

1111

? 1 4

? 2 3

!

提示

样例解释 #1

样例中隐藏的排列 $p = [4, 1, 3, 2]$。解释：

• 询问 $l = 1, r = 4$，$p$ 变为 $[1, 3, 2, 4]$，返回 $\texttt{1001}$。
• 询问 $l = 2, r = 3$，$p$ 变为 $[1, 2, 3, 4]$，返回 $\texttt{1111}$。
• 此时你认为 $p$ 已经升序排序，因此报告。

数据范围

• $1 \le n \le 1000$。
• 评测系统中隐藏的 $p$ 是一个 $1 \sim n$ 的排列。