Fata Morgana

Teodor wakes up in the desert alone, helpless and frightened. Before him appears “Fata Morgana“ which extends two tightly held fists and has him choose one. Choosing the left fist “Fata Morgana“ tells him “Congratulations, you avoided certain death. Solve for me the following task and I shall guide you away from the desert“.

You are given an array of $n$ positive integers where $n$ is even. You can reorder the integers however you want. What is the largest value for $(v_1 - v_2) \cdot (v_3 - v_4) \cdot (v_5 - v_6) \cdot ... \cdot (v_{n-1} - v_n)$ after reordering?

Print the reordered array.

Teodor, unable to think straight turns to you (seems he wasn’t alone after all) and asks you to quickly help him.

Input

The first line will contain $n$. ($2 \le n \le 3 \cdot 10^5$), $n$ is even.

The following line will contain $n$ positive integers ($0 \le v_i < 2^{32}$)

For tests worth $10$ points, ($1 \le n \le 18$).

Output

You will only output one line with the $n$ integers reordered (or not).
If there are multiple answers print the smallest lexicographical solution.
An array $a$ is considered lexicographically smaller than $b$ if $a_1 < b_1$ or there exists a $k \ge 1$ where $a_1 = b_1, a_2 = b_2, ..., a_k = b_k$ and $a_{k+1} < b_{k+1}$.

Example

stdin

4
3 2 1 1

stdout

1 2 1 3

Explanation

$(1 - 2) \cdot (1 - 3) = -1 \cdot -2 = 2$. This is the largest value you can achieve given this array.