1723: 【入门】奇偶数选大王

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:3 Solved:3

Description

在数字王国中,有值为1~n之间的整数,有奇数也有偶数;他们想分别在奇数和偶数中选出各自的大王,也就是选出奇数和偶数的最大数作为奇数大王和偶数大王。

请你编程帮助数字王国选出奇数和偶数的大王,并将所有的数字从小到大输出。

比如,假设输入5个数,分别是3 8 9 1 6,那么奇数大王(最大数)是9,偶数大王(最大数)是8,因此输出奇数大王和偶数大王以及所有数按照由小到大排序如下:

9 8

1 3 6 8 9

Input

输入有2行;

1行有一个整数nn10~1000之间的整数),代表数字王国中数字的总个数。

2行有n个整数(这些整数值在1~1000000之间,测试数据保证有奇数,也有偶数),数字之间用空格隔开。

Output

1行输出2个整数,分别是奇数大王和偶数大王,两个数之间用空格隔开。

2行将n个整数从小到大排序后输出,数与数之间用空格隔开。

Sample Input Copy

5
3 8 9 1 6

Sample Output Copy

9 8
1 3 6 8 9

HINT

样例输入1

5

3 8 9 1 6

样例输出1

9 8

1 3 6 8 9

样例输入2

8

11 3 12 8 1 1 5 10

样例输出2

11 12

1 1 3 5 8 10 11 12