Readability

The Martian alphabet consists of $10^9$ integers from $1$ to $10^9$. Odd integers are vowels, and even integers are consonants. A word is a sequence of such integers.

Changing the order of the integers in a word does not change its meaning, but it does change its pronunciation. If each pair of adjacent integers in a word contains one vowel and one consonant, the word is called readable.

Vasya Pupkin wants to open a restaurant of Earthern cuisine on Mars. He bought $n$ wooden integers for its name and placed them in a row on $n$ pedestals, numbered from $1$ to $n$. The integer on pedestal $i$ is $a_i$.

Moving an integer from pedestal $i$ to pedestal $j$ costs $|i - j|$ Martian rubles. During reordering, two or more integers may be on the same pedestal, but in the end each pedestal must have exactly one integer.

Find a readable word formed by reordering the integers that costs as few rubles as possible. If several such words exist, output the lexicographically smallest one.

A sequence $b$ is lexicographically smaller than a sequence $c$ of the same length if there exists an index $j$ such that $b_i = c_i$ for all $i < j$, and $b_j < c_j$.

The first line contains an integer $n$, the number of Martian letters in the word ($1 \leq n \leq 10^5$).

The second line contains $n$ space-separated integers $a_i$, the letters themselves ($1 \leq a_i \leq 10^9$).

It is guaranteed that a solution exists.

Output one line with $n$ space-separated integers: the required readable word.