N participants came to the Olympiad in Informatics. It is known in which schools the participants of the Olympiad study. There are N computers in the computer class, lined up along the wall. You need to seat the participants of the Olympiad so that no two participants from the same school sit next to each other.
Input
The program receives as input a positive integer number of participants in the Olympiad N1000. Next, N lines contain the numbers of schools where the participants of the Olympiad study. School numbers — integers from 1 to 3000.
Imprint
The program should output N numbers — the numbers of the schools of the participants of the Olympiad in the order in which they need to be seated in the computer class. The output sequence of school numbers must be a permutation of the given school numbers. The displayed answer should not contain two identical school numbers in a row.
If the problem has no solution, you need to print a single number 0.
Numbers can be displayed both in separate lines and in one line separated by a space. If there are several seating options, then you need to display any of them (but only one).
Examples
| # |
Input |
Output |
| 1 |
4
1005
1005
5
2005
| 1005 5 1005 2005 |
| 2 |
4
1005
1005
2005
1005
| 0 |