Array is beautiful if all a_i-a_{i-1} (2 \leq i \leq n) are distinct.
For example, [1, 3, 2, 9] and [8, 4, 6, 9] are beautiful, while [1, 2, 3, 9] and [1, 5, 5, 9] are not.
A sequence of integers b_1, b_2, \dots, b_n is called a permutation of the sequence c_1, c_2, \dots, c_n if the number of each unique number in these arrays is the same. For example, [1, 5, 3, 4, 2] is a permutation of [5, 2, 1, 4, 3], and [1, 3, 3, 5] is a permutation of [3, 5, 1, 3]. However, [1, 3, 4] is not a permutation of [2, 3, 4] (it doesn't contain , which should appear in the sequence and has , which should not appear).
Sakurako received an array. She wants to find an example of a permutation of the given array which is beautiful.
The first line contains one integer (2\le n\le 2\cdot 10^5) — the length of the array.
The second line contains integers a_1, a_2, \dots, a_n (1\le a_i\le 10^9) — elements of the array.
It is guaranteed that all numbers in the array are distinct. It is also guaranteed that an answer exists.
Output a beautiful array (which is a permutation of the original array) in one line. If there are multiple solutions, output any.
Example 1
Example 2
In the first example, array [3, 5, 4, 1, 2] is beautiful since if we take a_i-a_{i-1} for all , it will be:
5-3=2;
4-5=-1;
1-4=-3;
2-1=1.
As we see, all numbers are distinct.
In the second example, array [4, 2, 3] is beautiful since if we take a_i-a_{i-1} for all , it will be:
2-4=-2;
3-2=1.
As we see, all numbers are distinct.
You will receive at least points if your solution works correctly for n\le 10.
You will receive at least points if your solution works correctly for n\le 1000.