Wave Arrangement

Difficulty: 1300 3500 ms 128 MB

sorting

Rearrange into a wave: a₁ ≥ a₂ ≤ a₃ ≥ a₄ ... Print the lexicographically SMALLEST such arrangement.

Input: the first line has N; the second line has N integers.

Output: the wave-ordered values.

Constraints:

• 1 ≤ N ≤ 10⁵
• -10000 ≤ a_i ≤ 10000

Sample Tests

5
3 6 5 10 7

5 3 7 6 10

2
1 2

2 1

Read the Editorial