405952: GYM102191 C Seating Arrangement

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.

The first line of input contains n (3 ≤ n ≤ 3 × 10⁵), 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 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.

8
6 1 3 5 7 8 4 2

1 7 2 3 8 6 5 4

3
1 3 2

-1

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