## Problem L. LCA queries ≡

• problems
 Author: A. Usmanov Time limit: 1 sec Input / output: interactive Memory limit: 256 Mb

### Statement

This is an interactive problem. You will interact with a server by sending and receiving particular messages.

You are given a complete binary tree of height N having maximum possible number of nodes.

Nodes are numbered from 1 to 2N − 1.

Your task is to determine the number of root. You can perform requests to find least common ancestor (LCA) of any two nodes to achieve this. You are allowed to perform no more than N requests.

### Input format

The first line contains one integer N — height of the tree.

### Interaction protocol

To make a request print a line "? X Y", where X and Y — are integer numbers of nodes. After such a request you receive one integer — the number of least common ancestor of these two nodes.

When your program determines the root of the given tree, it should print "! X" and immediately stop.

Every query and final output must be a single line ending with single end-of-line (\n). Output buffers must be flushed after every line:

 Language C++ Pascal Java Python Code cout.flush() flush(output) System.out.flush() stdout.flush()

1 ≤ N ≤ 10

1 ≤ X, Y < 2N

### Explanation of the samples

The first sample contains the next tree:

### Sample tests

No. Standard input Standard output
1
3

2

5

7


? 3 6

? 1 5

? 2 4

! 7

2
1


! 1


0.078s 0.014s 15