Bob's Temple

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type

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.


Comments

There are no comments at the moment.