题目描述

工厂里有一些分拣物件的工作，其中一名工人的工作是将面前传送带上依次送来的 $n$ 个物件按照物件上的标号分别放到向左、向右两条传送带上，奇数的向左，偶数的向右。直到这一批物件分拣完，组长检查无误后打包装箱。

身为组长的小明自知责任重大，每次工人分拣完后他都会立即停下传送带，从工人左侧传送带的最左端开始核查物件的标号，直到查到工人右侧传送带上最右端，以确认是否分拣正确。已知物件传送过来的顺序，小明希望你帮忙记录一个关于物件标号的数字序列，表示他应当核查到物件的顺序，以便迅速完成工作。

输入输出格式

输入格式

第一行输入一个数 $n$ ，表示物件总数；

第二行输入 $n$ 个数，表示依次送来的 $n$ 个物件上的标号 $a_i$。

输出格式

输出一行 $n$ 个数，表示小明应核查到的正确的物件顺序，以空格隔开。

输入输出样例

6
1 2 3 4 5 6

1 3 5 6 4 2

数据规模

$1 \le n \le 10^5, 0 \leq a_i \leq 10^9$