Interactive Inversion Parity Query

This is an interactive problem. There is a hidden permutation \(p_1, p_2, \dots, p_n\) of \(\{1, 2, \dots, n\}\). You can ask queries regarding the parity of the number of inversions in any subarray of the permutation. In particular, you can query in the format ? l r, and the interactor will respond with the parity of the inversion count:

\[ \left(\sum_{l \le i p_j]\right) \bmod 2 \]

Here, \([p_i > p_j]\) is 1 if \(p_i > p_j\) and 0 otherwise. Your goal is to determine the hidden permutation by making such queries.

Note: In this simulation, the hidden permutation is provided as input. Your program should simply output the permutation.

inputFormat

The first line contains an integer \(n\), the size of the permutation. The second line contains \(n\) space-separated integers \(p_1, p_2, \dots, p_n\) representing the hidden permutation.

outputFormat

Output the hidden permutation in a single line with space-separated integers.

sample

3
1 2 3

1 2 3