409532: GYM103625 F Sinking Ship

The year is 1588, and you've found yourself aboard the ship of Sir Francis Drake, first Englishman to circumnavigate the globe and a government-endorsed... pirate?

Whatever the deal is, there's two things to know. Firstly, the ship has $$$n$$$ treasure rooms, labelled $$$1 \ldots N$$$, each containing a chest. The chests are also labelled $$$1 \ldots N$$$, according to their value (where chest $$$N$$$ is the most valuable). Of course, you'd like a sweet chunk of that treasure for yourself, but you and the rest of the crew have no clue which chests are in each room.

Secondly, Sir Francis Drake is also famous for helping the English defeat the Spanish Armada... which he is doing right now! In fact, it appears that you are currently in battle, and the Spanish just blew a massive hole in the side of your ship. It's only a matter of minutes before the ship completely sinks!

Of course, you don't actually care about fighting the Spanish – you, like the rest of the crew, just want to get some of the treasure before the ship goes under. Since everyone will be fighting over the most valuable chest, you decide to go after the second most valuable chest – the one labelled $$$N-1$$$.

As everyone scrambles around looking for chest $$$N$$$, you realize that you can save yourself some energy by asking them a simple question: in the rooms labelled between $$$l$$$ and $$$r$$$, what was the highest valued chest you've seen?

Quick! The ship is sinking fast, and you only have time to ask the other crewmates at most 40 questions. Can you locate the second most valuable chest before its too late?

Note that this is an interactive problem, which has different input / output format. Read below for details.

Initially, the only input will be a single integer $$$2 \leq N \leq 10^6$$$, representing the number of rooms in the ship.

The rest of the input is given through the interaction process.

For each question you want to ask to the crewmates, output "? $$$l$$$ $$$r$$$" (without quotes). After printing the query, your program should read in a single integer, which is the maximum valued treasure chest in the rooms labelled $$$l$$$ to $$$r$$$, inclusive.

After at most 40 questions, you may output "! $$$x$$$", where $$$x$$$ is the location of the second most valuable chest. Your program should exit afterwards, or else you may get unexpected verdicts. If you exceed 40 queries, you will receive Wrong Answer.

Remember to flush your output after printing each query. This can be done with fflush(stdout) in C++, System.out.flush() in Java, and stdout.flush() in Python.

5

5

4

3

2

1

? 3 5

? 1 2

? 2 4

? 4 4

? 3 3

! 1

The sample input and output show a possible set of interactions.

In this example, the chests in rooms 1 to $$$N$$$ are 4, 3, 1, 2, 5, respectively.