Reconstructing the Sequence with One Tolerance

This is an interactive problem.

You are given a sequence of n distinct positive integers \(a_1, a_2, \ldots, a_n\). You can ask queries: for any two indices \(i\) and \(j\) (with \(1 \le i,j \le n\) and \(i \neq j\)), you can ask for the value of \(\min(a_i,a_j)\). The sequence \(a\) is fixed before any query is made. You may ask at most 3000 queries.

Your task is not to fully determine \(a\) – since the maximum element is impossible to determine by these queries – but to output another sequence \(b_1,b_2,\ldots,b_n\) such that for all \(1 \le i \le n\), \(b_i \le a_i\), and there is at most one index \(i\) for which \(b_i \neq a_i\). In other words, you must recover all the values of \(a\) except perhaps the maximum one; for the maximum, you may output any integer (within the range \([-2^{31},2^{31})\)) that is less than or equal to the true maximum value.

Note: In this problem, interactive means that during the contest you would be interacting with the judge by issuing queries. However, for the purposes of testing, the hidden array will be provided as input after the integer \(n\). Thus, you can simulate the interactive behavior by reading the entire array from input.

Interaction format (for an interactive judge):

• The first line contains a single positive integer \(n\).
• You may issue several queries of the form ? i j (where \(i \neq j\) and \(1 \le i,j \le n\)). After each query, you will receive an integer representing \(\min(a_i,a_j)\).
• When you are ready, output a line of the form ! b_1 b_2 \ldots b_n (answers do not count as queries).
• Remember that you must ensure that each \(b_i \le a_i\) and that at most one index \(i\) satisfies \(b_i \neq a_i\). Also, each \(b_i\) must lie in the range \([-2^{31},2^{31})\).

Intuition: Since you cannot determine the maximum element exactly, you can identify the index \(M\) at which \(a_M\) is maximum using tournament comparisons. Once \(M\) is known, for every index \(i \neq M\), you can determine \(a_i\) by querying \(? i M\) (because \(a_i < a_M\)). For the index \(M\), simply output any number less than \(a_M\) (for instance, the maximum of the other values). This ensures that the condition is satisfied with at most one mismatch.

inputFormat

The first line contains a positive integer \(n\). The second line contains \(n\) distinct positive integers representing the sequence \(a_1, a_2, \ldots, a_n\). In an actual interactive problem you would have to make queries; however, for testing purposes the entire sequence is provided.

outputFormat

Output one line beginning with an exclamation mark (!) followed by \(n\) integers \(b_1, b_2, \ldots, b_n\) separated by spaces. The output sequence must satisfy that for every \(i\), \(b_i \le a_i\), and at most one index \(i\) has \(b_i \neq a_i\). Each \(b_i\) must be in the range \([-2^{31},2^{31})\).

sample

5
2 5 1 3 4

! 2 4 1 3 4