Cowboy Vlad has a birthday! n children gathered for the holiday. To congratulate the cowboy, the children decided to dance around Vlad. Among the children who came to Vlad, there are both tall and short ones, so if they stand in a round dance as they please, many of them may be uncomfortable, because if a very tall and very short child are standing next to each other in a round dance, it is difficult for them to hold hands. Therefore, the children decided to stand in a round dance so that the maximum difference in the heights of two neighboring children was minimal.
More formally, let n children line up in a round dance. We number them with integers from 1 to n so that the child with number i + 1 is to the right of the child with number i, and the child with number 1 is to the right of the child with number n. Then the inconvenience of this round dance is the maximum difference between the heights of children who are standing nearby. Note that the difference in height between two children is the difference between the height of the taller and shorter child, so the difference in height between two children is always non-negative.
Help the children and determine in what order they should line up in a circle to minimize the inconvenience of the resulting round dance. Please note that all n children must be in a round dance.
Input
The first line contains a single integer n (2 ≤ n≤ 10
5) — the number of children who came to the birthday of the cowboy Vlad.
The second line contains n integers a
i (1≤a
i≤10
9) — growth of each child. Children's height is given in nanometers and reduced by 10
9, so the height of a child with a
i=1 is just over a meter, and the height of a child with a
i sub>=109 is two meters.
Imprint
Print n integers — the values of the growth of children in the order in which they should stand in a round dance. In this order, children numbered i and i+1 will be neighbors, as well as children numbered 1 and n. If there are several optimal round dances, then print any of them.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
5
2 1 1 3 2
| 1 2 3 2 1 |
Here, the inconvenience of the round dance is 1, since the difference in height between neighboring children is 1, 1, 1, 1 and 0 respectively. Note that the sequences [23211] , [32112] set the same round dances and differ only in the choice of child number 1. |
| 2 |
3
30 10 20
| 10 30 20 |
The inconvenience of the round dance is 20, since the difference in the height of children with a height of 10 and 30 is 20. |