Problem I
Bracket Guessing

This is an interactive problem.

There is a hidden bracket string $s$ of size $n$. You can ask up to $n$ queries of the form $?$ $l$ $r$, and the judge will tell you whether the contiguous substring from position $l$ to position $r$ is a regular bracket sequence. Find the longest contiguous substring of $s$ that is a regular bracket sequence.

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters ‘1’ and ‘+’ between the original characters of the sequence. For example, bracket sequences “()()”, “(())” are regular (the resulting expressions are: “(1)+(1)”, “((1+1)+1)”), and “)(” and “(” are not.

Interaction

The judge will start by outputting a line with a single integer $n$ ($1\le n \le 10^4$) —the size of the bracket sequence.

You can then ask at most $n$ queries. For each query, output a single line of the form $?$ $l$ $r$ ($1 \le l \le r \le n$). The judge will then output $1$ if the substring from position $l$ to $r$, inclusive, is a regular bracket sequence, and $0$ otherwise.

Make sure to flush the output after printing every query, or you will receive a Time Limit Exceeded verdict. In order to flush the output, use:

• fflush(stdout) in C++

• System.out.flush() in Java

• stdout.flush() in Python

• For other languages, see the documentation.

Once you have found the longest substring $[l, r]$ that is a regular bracket sequence, output $!$ $l$ $r$. If there are no substrings that are regular bracket sequences, print $!$ $none$. Printing the answer does not count towards your limit of $n$ queries.

If there are multiple solutions, you may choose any.

The strings in the samples are $)(()))(()$, $)(($, and $()()$, respectively.

9

? 1 8

0

? 8 9

1

? 2 5

1

? 1 6

0

? 6 7

0

! 2 5

3

? 1 2

0

? 2 3

0

! none

4

? 1 2

1

? 3 4

1

! 1 4