After dealing with his $n$ numbers for too long, Bob decides to ask you to make his array into a temple: a temple must satisfy the following conditions to be valid:

• It starts and ends with $1$,
• Adjacent elements have a maximum difference of $1$,
• There is $1$ maximum number and peaks at that number,
• It is non-decreasing before the peak and is non-increasing after the peak.

Help Bob re-order his array into a temple!

Input Specification

The first line will contain $n$ $(3\le n\le 1000000)$, the number of elements in the array.

The next line will contain $n$ space-separated integers $A_i$ $(1\le A_i\le 1000000)$, the value of the $i^{\text{th}}$ element.

Output Specification

Output $n$ integers, a permutation of Bob's array that is a valid temple.

If there are multiple valid solutions, output the lexicographically largest one.

Note: It is guaranteed that there is at least one valid solution.

Sample Input 1

5
1 3 2 2 1

Sample Output 1

1 2 3 2 1

Sample Input 2

11
1 1 2 2 2 3 4 5 4 3 4

Sample Output 2

1 2 3 4 5 4 4 3 2 2 1

Note: There are multiple valid solutions for this case, but this is the lexicographically largest one.