31975번 - Staring Contest 서브태스크점수다국어인터랙티브

문제

A staring contest is a classical battle of imperturbability in which two people stare into each other's eyes while maintaining a facial expression of assured serenity. The goal is to maintain eye contact for longer than your opponent. The contest ends when one participant breaks composure, typically by looking away, smiling, speaking, or giggling.

As a coach of the national staring contest you need to determine the imperturbability of each of your team's $n$ members for the upcoming world finals. The $i$th athlete can maintain eye contact for exactly $a_i$ seconds, but these values are unknown to you in the beginning. For instance, you could have a team of $n=3$ members:

When athletes $i$ and $j$ compete, the confrontation lasts exactly $\min(a_i, a_j)$ seconds, at which moment the weaker contestant breaks composure and both contestants start smiling and giggling within a fraction of a second. For instance, if Anna competes against Esther, the contest lasts for 431ドル$ seconds. Importantly, to an outside observer the actual winner of the confrontation (in this case, Esther) is impossible to determine, only the duration of the contest is measurable.

Your goal is to estimate the values $a_1,\ldots, a_n$ using as few staring contests as possible. Clearly, the strength of the strongest athlete can never be determined, so you are allowed to underestimate one of the $a_i$.

인터랙션

This is an interactive problem. The interaction begins with you reading a single line containing the integer $n$. You may then ask queries of the form "? $i$ $j$" such that 1ドル\leq i\leq n$ and 1ドル\leq j\leq n$ and $i\neq j$. The response to a query is a single integer: the value $\min(a_i, a_j)$. The interaction ends with you printing a single line consisting of ! followed by $n$ estimates in the form of integers $b_1,ドル $\ldots,ドル $b_n,ドル separated by spaces. This must be your final line of output.

Your submission is correct if $b_i=a_i$ for every contestant $i$ except one, which you may underestimate. To be precise, we require $b_i\leq a_i$ for all 1ドル\leq i\leq n$ and allow $b_k \neq a_k$ for at most one $k$.

The interactor is non-adaptive, meaning that the $a_1,\ldots, a_n$ are determined before the interaction begins.

입력

출력

제한

The number $n$ of athletes satisfies 2ドル\leq n\leq 1500$. The imperturbability $a_i$ of each athlete satisfies 1ドル\leq a_i\leq 86,400円,ドル they are all different. You can use at most 3000ドル$ queries; your final line of output, i.e., the line starting with !, is not counted as a query.

서브태스크

힌트