Even-Odd Partition Interactive Game

Ivan wants to play a game with you. He takes all integers from \(1\) to \(n\) inclusive, shuffles them and then places all even numbers into an array \(e\) and all odd numbers into an array \(o\). Your task is to determine the arrays \(e\) and \(o\).

You can ask queries of the following type:

• "? i j" where \(1 \le i \le \lfloor n/2 \rfloor\) and \(1 \le j \le \lceil n/2 \rceil\).

For each query, Ivan will respond with:

• "<" if \(e[i] < o[j]\)
• ">" otherwise

You are allowed at most \(300\,000\) queries. Once you are ready, output your final answer in the following format:

! e1 e2 \(\cdots\) e\lfloor n/2 \rfloor o1 o2 \(\cdots\) o\lceil n/2 \rceil

Interaction Protocol:

1. The first input is a single integer \(n\) (\(1 \le n \le 10\,000\)).
2. You may interact with Ivan by printing queries and reading his responses. Don’t forget to flush the output after each request.
3. Your solution must print exactly one final answer (starting with an exclamation mark '!') and then exit gracefully.
4. For the purpose of this problem, the numbers have been shuffled using Java's built-in shuffle function with a fixed seed.

Note: In offline testing the entire permutation is provided as input on the second line, so you can simulate Ivan's behavior by deriving arrays \(e\) and \(o\) from the given permutation.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(n\) -- the number of integers.
2. The second line contains \(n\) space-separated integers representing the shuffled permutation of \(1\) to \(n\).

outputFormat

Output a single line in the following format:

! e1 e2 ... e\(\lfloor n/2 \rfloor\) o1 o2 ... o\(\lceil n/2 \rceil\)

This line should begin with an exclamation mark followed by the elements of array \(e\) and then the elements of array \(o\), all separated by spaces.

sample

5
3 2 5 4 1

! 2 4 3 5 1