408029: GYM102964 C Find the order

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Find the ordertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given an array of $$$n$$$ positive integers. You should determine is it possible to reorder it's elements in such a way that condition $$$a_1 < a_2 > a_3 < a_4 > a_5... $$$ is true. In other words, first element should be strictly less than the second, the second element should be strictly greater than the third etc. If such order exists output $$$n$$$ numbers – the resulting array. If no, just output $$$-1$$$. If there are more than one correct order output any of correct arrays.

Input

In first line you are given number $$$n$$$, $$$1 \le n \le 10^5$$$ – number of elements in array. In the second line you are given $$$n$$$ positive integers $$$1 \le a_i \le 10^9$$$ – array itself.

Output

Output correct order if it exists or $$$-1$$$ if no. Output elements not indices.

ExamplesInput
5
1 2 3 4 1
Output
1 3 1 4 2
Input
4
1 1 1 1
Output
-1

加入题单

上一题 下一题 算法标签: