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.
Read  Sample Interaction 1  Write 

9
? 1 8
0
? 8 9
1
? 2 5
1
? 1 6
0
? 6 7
0
! 2 5
Read  Sample Interaction 2  Write 

3
? 1 2
0
? 2 3
0
! none
Read  Sample Interaction 3  Write 

4
? 1 2
1
? 3 4
1
! 1 4