403659: GYM101234 F Lonely Dreamoon 2

Dreamoon, who doesn't have a girlfriend, often goes for a walk along some streets in Taipei while thinking about problems from algorithm competitions. Unfortunately, there are so many couples acting lovey-dovey on the street that Dreamoon can not focus on thinking about those problems.

One day, despite the love birds everywhere, Dreamoon discovered a problem input containing an integer sequence: a₁, a₂, a₃, ..., a_N.

Dreamoon thought: because I'm single, every pair of consecutive numbers should have a large difference! This is, Dreamoon wants to reorder the sequence to make the value as large as possible.

So Dreamoon turned on Drazil, who does have a girlfriend, and forced Drazil to fulfill the above condition by reordering the integer sequence. Please help poor Drazil  > _ < 

The input consists of two lines. The first line contains an integer N. The second line consists of N integers a₁, a₂, ..., a_N.

• 2 ≤ N ≤ 2 × 10⁵
•  - 10⁹ ≤ a_i ≤ 10⁹

Output a single line consisting of N integers, denoting the integer sequence a after reordering. For this reordering, the value must be the largest possible among all reorderings of the input sequence. If there are several possible answers, output any one of them.

3
3 1 5

3 5 1

4
-1 -1 1 1

1 -1 1 -1