# #6669. Nauuo and Binary Tree

#### 题目描述

「Codeforces Round #564 赛前四天撞题 D」

Nauuo 是一个喜欢二叉树的女孩子。

#### 样例 1 输入

4
1
2
3


#### 样例 1 输出

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


#### 样例 2 输入

5
4
1


#### 样例 2 输出

? 4 3
? 2 4
! 1 5 2 1


#### 数据范围与提示

This is an interactive problem.

Nauuo is a girl who loves binary trees.

One day, she created a binary tree consisting of nodes. The nodes are numbered from to . The root of the tree is the node .

However, Nauuo can't remember the tree exactly. She only remembers the distance between every two nodes, you can make some queries on the distance to find the whole binary tree.

The distance between two nodes is the number of edges of the shortest path between the two nodes.

You are allowed to make no more than queries, and you only have to tell Nauuo the parent of each node except the root.

#### Interaction

The interaction starts with a line containing one integer () --- the number of nodes.

After that, you can make queries.

To make a query, print a line "" (), then the output.

After each query, read a single integer () --- the distance between and .

When you find the whole binary tree, print a line "", the output and terminate. is an array containing integers, where the -th element of is the parent of node .

The interactor will cost no more than if you make no more than queries.

Your solution will get or if you make more than queries.

Your solution will get if you don't print anything or forget to flush the output.

To you need to do the following right after printing a query and a line end:

• or in C++;
• in Java;
• in Pascal;
• in Python;
• see documentation for other languages.

#### Hacks

The first line contains a single integer () --- the number of nodes.

The second line contains an array containing integers, where the -th element of is the parent of node .

For hacks, you have to guarantee that the given parents can form a tree.

#### Examples

##### Input
4
1
2
3


#### Output

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


The binary tree is as follows.

In the first query, the distance between and is ().

In the second query, the distance between and is ().

In the third query, the distance between and is ().

##### Input
5
4
1

##### Output
? 4 3
? 2 4
! 1 5 2 1


The binary tree is as follows.