Description

This is an interactive problem.

There is a sequence $a$ of length $n$. You need to find an interval such that the absolute value of its interval sum is maximized.

However, you do not have access to this sequence. Instead, you need to determine the answer by making queries to the interactive library.

Once you have found the answer, you can respond as follows:

• ! l r: You must ensure that $\displaystyle\left|\sum_{i=l}^r a_i\right| = \max_{x=1}^n \max_{y=x}^n \left|\sum_{i=x}^y a_i\right|$, and then immediately terminate your program.

Interaction

This problem uses standard input and output for interaction.

Please ensure the interaction format is correct, otherwise you may receive a WA or TLE verdict.

Basic Information

Initially, you will read an integer $n$ on the first line, representing the length of the sequence $a$.

Query Format

You may perform the following query, but the total number of queries must not exceed $2n$:

• ? l r: Query the interactive library to check whether $\displaystyle\sum_{i=l}^r a_i \ge 0$.

For each query, you can directly output your operation to standard output, and flush the output buffer after each operation.

You can use the following statements to flush the buffer:

• For C/C++: fflush(stdout);
• For C++: std::cout << std::flush;
• For Java: System.out.flush();
• For Python: stdout.flush();
• For Pascal: flush(output);
• For other languages, please refer to the relevant documentation.

Specifically, for C++, if you use std::endl instead of '\n' when outputting a newline, the buffer will also be flushed automatically.

Response Format

For each query, the interactive library will respond with a boolean value.

Input Format

See [Interaction].

Output Format

See [Interaction].

2

1

0

0

? 1 1

? 2 2

? 1 2

! 2 2

Hint

Data Range

This problem uses bundled testing.

• For $100\%$ of the data, $1 \le n \le 10^5$.

• It is guaranteed that there are no cases where the maximum absolute value of any interval sum is $0$.

Translated by ChatGPT 4.1