Zigzag Sequence Transformation

You are given a list of n distinct positive integers. Your task is to transform this list into a Zigzag Sequence by following these steps:

1. First, sort the list in increasing order.

2. Partition the sorted list into two parts. The first part (left) consists of the first \(\lceil n/2 \rceil\) elements and the second part (right) consists of the remaining elements.

3. Reverse the second part.

4. Construct the final sequence by alternating elements from the left and right parts, starting with the first element of the left part. If one part runs out of elements, simply append the remaining elements from the other part.

For example, given the list [4, 1, 7, 3, 8, 2], after sorting we obtain [1, 2, 3, 4, 7, 8]. The left part will be [1, 2, 3] and the right part (after reversing) will be [8, 7, 4]. Alternating them gives the final sequence: [1, 8, 2, 7, 3, 4].

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains a single integer n indicating the number of elements.
• The second line contains n space-separated integers.

outputFormat

Output the zigzag sequence on a single line to stdout with the numbers separated by a single space.

## sample

6
4 1 7 3 8 2

1 8 2 7 3 4