Background

Yet Another Interactive Problem About Permutation.

Problem Description

This is an interactive problem.

The judge system has a hidden permutation $p$ of $1 \sim n$.

Each time, you may query two integers $l, r$ such that $1 \le l \le r \le n$. The judge system will do the following:

1. Cyclically shift the subsegment $p[l, \ldots, r]$ by one.
2. The judge system will return a $\texttt{01}$ sequence $s$ of length $n$, where $s_i = 1$ if and only if currently $p_i = i$.

In this problem, cyclically shifting a non-empty sequence by one means: insert the first element of the sequence at the end, and delete the first element.

Your goal is to make the final permutation $p$ sorted in ascending order through a series of operations, i.e., for all $i \in [1, n]$, we have $p_i = i$.

Interaction

Your program needs to interact with the judge system via standard input and output.

First, your program should read an integer $n$, which is the length of the hidden permutation. Then, your program should start making queries. Each query has the format:

? l r

where $l, r$ are positive integers satisfying $1 \le l \le r \le n$. After each query, the judge system will return a $\texttt{01}$ string of length $n$, and your program should read it from standard input.

When you think that $p$ is already sorted in ascending order, you should report it in the format:

!

After outputting the answer, your program should terminate immediately.

You can make at most $2026$ queries. If the number of queries exceeds the limit, or the answer is wrong, or the format does not meet the requirements, the judge system will return Wrong Answer.

Note: After each output, you must flush the buffer. For example, in C++ use cout << endl or fflush(stdout), and in Python use print(..., flush=True).

You may ignore the runtime of the interactive library.

4

1001

1111

? 1 4

? 2 3

!

Hint

Sample Explanation #1

In the sample, the hidden permutation is $p = [4, 1, 3, 2]$. Explanation:

• Query $l = 1, r = 4$. Then $p$ becomes $[1, 3, 2, 4]$, and the judge returns $\texttt{1001}$.
• Query $l = 2, r = 3$. Then $p$ becomes $[1, 2, 3, 4]$, and the judge returns $\texttt{1111}$.
• Now you think that $p$ has been sorted in ascending order, so you report it.

Constraints

• $1 \le n \le 1000$.
• The hidden $p$ in the judge system is a permutation of $1 \sim n$.

Translated by ChatGPT 5