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 1\,000\,000)~, the number of elements in the array.

The next line will contain ~n~ space-separated integers ~A_i~ ~(1 \le A_i \le 1\,000\,000)~, 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.