25444번 - Mađioničar 서브태스크다국어인터랙티브

You might have heard that in his free time, Mr. Malnar does magic. His recent appearance in the famous TV show Penn & Teller: Fool Us took the world by storm. He introduced himself as The Magical Mr. Malnar, pulled off an incredible mentalist trick, and swept everyone off their feet.

He started off by calling up an eager volounteer from the audience and asking them to think of any string of their choice that consists of exactly $N$ letters. He then proceeded to entertain the audience, occasionally glancing at the volounteer, and at the end he declared: “the longest sub-palindrome¹ of your string has length $L$”. After the volounteer confirmed this is indeed correct, the audience was stunned.

However, observant viewers and close friends of Mr. Malnar suspect this was not mind reading, but a clever selection of words that, when combined with excellent reading of facial expressions, gives away enough information to pull off the trick.

While it seemed like Mr. Malnar was merely fooling around, from time to time he would mention some interval of numbers $[l, r]$, where $1 ≤ l ≤ r ≤ N$ and briefly glance at the volounteer. There are rumors saying he is able to determine whether or not the substring of the volounteer’s string that consists of the $l$-th through the $r$-th letter (inclusive) is a palindrome, based on their facial expression alone.

You need to write a program which will confirm that Mr. Malnar, if the rumors are true, was able to gather enough information to determine the longest sub-palindrome of the secret string choosen by the volounteer.

¹A palindrome is a string that reads the same backward or forward. A substring of a string is a string made up from the $l$-th through the $r$-rh letter of that string, for some $1 ≤ l ≤ r ≤ N$. A sub-palindrome is a substring which is also a palindrome.

This is an interactive task. Your program must communicate with a program made by the organizers which simulates the behaviour of the volounteer from the task description.

Before interaction, your program should read an integer $N$, the length of the secret string, from the standard input task statement.

After that, your program can send query requests by writing to the standard output. Each query must be printed in a separate line and have the form “? $l$ $r$”, where $1 ≤ l ≤ r ≤ N$ holds. After each query has been written, your program should flush the output and read the answer from the standard input. The answer is a $1$ if the substring $[l, r]$ is a palindrome, or $0$ if it’s not. Your program can make at most $200\,000$ such queries.

After your program has deduced the length of the longest sub-palindrome, it should write a line to the standard output in the form “! $L$”, where $L$ is the said length. After that, your program should flush the output once more and gracefully terminate its execution.