405952: GYM102191 C Seating Arrangement

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

Description

C. Seating Arrangementtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have a class of n number of students arranged in a circle. Last month, this seating arrangement caused too much noise in the class and now you want to rearrange the students.

To avoid chatting, you want to arrange the students such that no two students that were next to each other in last month's arrangement are next to each other in the new arrangement.

If possible, print one arrangement that satisfies the conditions.

Input

The first line of input contains n (3 ≤ n ≤ 3 × 105), the size of the class.

The next line of input contains a permutation of the numbers from 1 to n, representing the IDs of the students in last month's seating arrangement. Note that the permutation is circular, and the first student is adjacent to the last student.

Output

Output the students' IDs in one possible circular seating arrangement that satisfies the conditions. If there is no possible answer, output -1 on a single line.

If there is more than one possible solution, output any of them.

ExamplesInput
8
6 1 3 5 7 8 4 2
Output
1 7 2 3 8 6 5 4
Input
3
1 3 2
Output
-1
Note

The sample test is illustrated in the picture above. Note that no two students are adjacent in both arrangements.

加入题单

上一题 下一题 算法标签: