19064번 - 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.

Why do Martians have such a big alphabet? It gives the language an interesting property: 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, such word is called readable.

Vasya Pupkin decided 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 placed on $i$-th pedestal is denoted as $a_i$.

Now Vasya wants to reorder the integers, because he wants the name of the restaurant to be readable. But moving an integer from pedestal $i$ to pedestal $j$ costs $|i - j|$ Martian rubles. Integers are flat, so two or more of them can be placed on one pedestal while reordering, but in the end, each pedestal must have exactly one integer on it.

Help Vasya to find a readable word formed by reordering the integers that requires him to pay as little Martian rubles as possible. If there are several such words, choose one that is the smallest lexicographically, because that will put the name of the restaurant earlier in the telephone directory.

A sequence of integers $b_i$ is lexicographically smaller than a sequence of the same length $c_i$ if there exists such index $j$ that $b_i = c_i$ for all $i < j,ドル but $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 the solution exists.

출력

Output one line. It must contain $n$ space-separated integers: the required readable word.

제한

힌트