C. Zigzag Sort
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ethan and Justin are arguing over how to sort a list of $$$n$$$ distinct integers. Ethan wants ascending order; Justin wants descending order. Unable to agree, they settle on a compromise: arrange the numbers in a zigzag pattern, so that the sequence alternately rises and falls.

A sequence $$$a_1, a_2, \ldots, a_n$$$ is zigzag if odd-indexed elements are local peaks (each is greater than its immediate neighbors) and even-indexed elements are local valleys (each is less than its immediate neighbors).

Given the list, output any re-ordering of the given integers so that the final sequence forms a zigzag sequence.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 200$$$) — the number of integers.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10000$$$) — the list.

Output

Print $$$n$$$ integers on a single line — any permutation of the input that forms a zigzag sequence. It is guaranteed that a solution always exists.

There are multiple possible correct answers — any correct answer will be accepted.

Examples
Input
5
1 2 3 4 5
Output
5 3 4 1 2
Input
4
2 7 1 8
Output
8 1 7 2