P14007 Query Game

**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

See [Interaction].

See [Interaction].

### Data Range **This problem uses bundled testing.** | $\tt Subtask$ | $n$ | Query Limit | $\tt Points$ | | :----------: | :----------: | :----------: | :----------: | | $0$ | $5$ | $\cfrac{n(n+1)}{2}$ | $10$ | | $1$ | $2000$ | $\cfrac{n(n+1)}{2}$ | $30$ | | $2$ | $10^5$ | $2n$ | $60$ | - 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