火星字母表由 $1$ 到 $10^9$ 的整数组成。奇数是元音，偶数是辅音。单词即为这些整数的序列。

为什么火星人有这么大的字母表？这赋予了该语言一个有趣的特性：改变单词中整数的顺序不会改变其含义，但会改变其发音。如果一个单词中每一对相邻的整数都包含一个元音和一个辅音，则称该单词是“可读的”。

Vasya Pupkin 决定在火星上开一家地球菜餐厅。他买了 $n$ 个木制整数作为餐厅名称，并将它们按顺序放在 $n$ 个底座上，底座编号从 $1$ 到 $n$。第 $i$ 个底座上的整数记为 $a_i$。

现在 Vasya 想要重新排列这些整数，因为他希望餐厅名称是可读的。将一个整数从底座 $i$ 移动到底座 $j$ 的代价是 $|i - j|$ 火星卢布。整数是扁平的，因此在重新排列过程中，两个或多个整数可以放在同一个底座上，但最终每个底座上必须恰好有一个整数。

请帮助 Vasya 找到一个由这些整数重新排列组成的可读单词，使得他支付的火星卢布总数最少。如果存在多个这样的单词，请选择字典序最小的一个，因为这会让餐厅名称在电话簿中排在更前面。

如果序列 $b_i$ 与序列 $c_i$ 长度相同，且存在索引 $j$，使得对于所有 $i < j$ 都有 $b_i = c_i$，且 $b_j < c_j$，则称序列 $b_i$ 字典序小于序列 $c_i$。

输入格式

第一行包含一个整数 $n$，表示单词中火星字母的数量 ($1 \le n \le 10^5$)。 第二行包含 $n$ 个空格分隔的整数 $a_i$，即字母本身 ($1 \le a_i \le 10^9$)。 保证解一定存在。

输出格式

输出一行。包含 $n$ 个空格分隔的整数：所求的可读单词。

样例

输入 1

5
5 3 1 4 2

输出 1

5 2 1 4 3