Palindrome Suits

Limits: 4 sec., 256 MiB

This statement was translated automatically from Ukrainian.

This is an interactive problem (where your program interacts with the jury’s program via standard input and output).

Zenyk and Marichka have stallions of various suits — bay, black, buckskin, and many others. They (Zenyk, Marichka, and the horses) want to play a game with you.

Zenyk and Marichka lined up \(n\) horses in a row. The row is given by a string \(s\) of length \(n\) consisting of lowercase Latin letters. The characters of the string represent the suits of the horses in the order of the row. For example, the letter a can denote a bay stallion, b — a black one, c — a buckskin one, and so on.

Once the horses are lined up, Zenyk and Marichka will no longer change their order in the row. Thus, the string \(s\) is fixed in advance and will not change throughout the game.

You are given the number \(n\), but you cannot see the row and do not know the string \(s\). The goal of the game is to guess the length of the longest substring of \(s\) that is a palindrome.

A string \(t\) is called a substring of a string \(s\) if it is possible to delete some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of string \(s\) to form the string \(t\). For example, the strings algo, tester, got, e are substrings of algotester, while lost, alcotester are not.

A string \(t\) is called a palindrome if it reads the same forwards and backwards. For example, the strings abacaba, pylyp, aa, b are palindromes, while algotester, oblasna are not.

You can ask questions. Each question is a pair of numbers \(l, r\) such that \(1 \le l \le r \le n\). In response, Zenyk and Marichka will tell you whether the substring \(s_l s_{l+1} \dots s_r\) is a palindrome.

To make the game more interesting, Zenyk and Marichka set a limit — you can ask no more than \(25000\) questions.

Input

You are given an integer \(n\) — the number of horses in the row.

After reading the number \(n\), the interaction between your program and Zenyk and Marichka begins, during which your program asks questions and Zenyk and Marichka answer them.

To ask a question, print "?\(\ l \ r\)", where \(l, r\) are integers satisfying \(1 \le l \le r \le n\). This means you want to know whether the substring \(s_l s_{l+1} \dots s_r\) is a palindrome.

In response to the question, Zenyk and Marichka will give an integer \(x\) (\(x \in \{0, 1\}\)), which you must read in your program. If \(x = 1\), then the substring is a palindrome; if \(x = 0\), then it is not.

If the question is invalid (i.e., the maximum number of questions has been exceeded or the question parameters are invalid), Zenyk and Marichka will reply with -1 and terminate the game. In this case, terminate your program to receive the Wrong Answer verdict. If you fail to do this, you may receive a Runtime Error verdict.

Make sure to flush the output after printing each line. You can use:

• fflush(stdout), cout << endl or cout.flush() in C++;

• System.out.flush() in Java;

• flush(output) in Pascal;

• sys.stdout.flush() in Python;

• Console.Out.Flush() in C#.

Output

To give the answer, print a string in the format "!\(\ p\)", where \(p\) is the length of the longest substring of \(s\) that is a palindrome. After that, your program must terminate.

Constraints

\(1 \le n \le 7447\).

Scoring consists of the following blocks:

• 1 point for the example from the statement,

• 17 points: \(n \le 100\),

• 36 points: \(n \le 1000\), the answer to the problem is an even number,

• 21 points: \(n \le 1000\),

• 25 points: without additional constraints.

Points for a block are awarded only if your program passes all tests in that block.

Notes

Below is an example of interaction for \(n=7\), \(s =\)cabaaba.