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 × 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 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.
The sample test is illustrated in the picture above. Note that no two students are adjacent in both arrangements.
## 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.
[samples]
## Note
The sample test is illustrated in the picture above. Note that no two students are adjacent in both arrangements.
**Definitions**
Let $ n \in \mathbb{Z} $ with $ 3 \leq n \leq 3 \times 10^5 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a circular permutation of $ \{1, 2, \dots, n\} $, representing the previous seating arrangement, where $ a_i $ is adjacent to $ a_{i+1} $ for $ i = 1, \dots, n-1 $, and $ a_n $ is adjacent to $ a_1 $.
**Constraints**
1. $ 3 \leq n \leq 3 \times 10^5 $
2. $ A $ is a permutation of $ \{1, 2, \dots, n\} $
3. In the new arrangement $ B = (b_1, b_2, \dots, b_n) $, no two consecutive elements $ b_i, b_{i+1} $ (with $ b_{n+1} = b_1 $) may be adjacent in $ A $, i.e., for all $ i \in \{1, \dots, n\} $, $ \{b_i, b_{i+1}\} \not\in \{ \{a_j, a_{j+1}\} \mid j = 1, \dots, n \} $ (indices modulo $ n $).
**Objective**
Find a circular permutation $ B $ of $ \{1, 2, \dots, n\} $ satisfying the adjacency constraint, or output $-1$ if no such arrangement exists.