题目描述

这是一道交互题。

有一个长度为 $n$ 的正整数序列 $a_1,a_2,\cdots,a_n$，它们两两不同。每次询问你可以给定正整数 $1\le i, j\le n$，其中 $i\neq j$，交互库会告诉你 $\min(a_i,a_j)$。

你需要确定序列 $a$。然而，显然最大的 $a_i$ 是无法确定的，因此你只需求出一个整数序列 $b_1,b_2,\cdots,b_n$，满足对于所有 $i=1,2,\cdots,n$，有 $b_i\le a_i$，且最多有一个 $i$ 满足 $b_i\neq a_i$。

（搬题人注：你还需保证 $b_i$ 在 $[-2^{31},2^{31})$ 中。）

交互库不是自适应的。换而言之，序列 $a$ 在交互前已确定。

【交互格式】

首先选手程序读入一行一个正整数 $n$。

接下来选手可以进行若干次询问，每次询问形如 $\texttt{?}\ i\ j$，其中 $i,j$ 为满足 $1\le i,j\le n$ 且 $i\neq j$ 的正整数。

每次询问后，你需要从标准输入中读入一个正整数，表示 $\min(a_i,a_j)$ 的值。你可以询问不超过 $3\,000$ 次。

如果你确定了你要回答的序列 $b$，则输出一行 $\texttt{!}\ b_1\ b_2\ \cdots\ b_n$ 表示你的回答。回答不计做询问。

每次询问后，你需要清空缓冲区。

输入格式

见「交互格式」。

输出格式

见「交互格式」。

3
431
121
121

? 1 2
? 1 3
? 2 3
! 431 431 121

提示

【样例解释】

一个可能的 $a$ 为 $[431,623,121]$。

【数据范围】

对于 $100\%$ 的数据，$2\le n\le 1\,500$，$1\le a_i\le 86\,400$，$a_i$ 两两不同。

对于前两个子任务，你将获得满分当且仅当你正确的解决了该子任务中的每一个测试点，否则将获得零分。

对于第三个子任务，你的得分为其所有测试点的最低分。其中，对于每个测试点，如果你的程序没有正确解决这个测试点，你将获得 $0$ 分。否则，设你询问了 $q$ 次。若 $q\le n+25$，你将获得 $80$ 分。若 $q>3\, 000$，你将获得 $0$ 分。否则，你将获得 $118.2-12\ln(q-n)$ 分，四舍五入至最近的整数。