Maximize Gem Beauty

You are given an integer n and a list of n positive integers representing the intensities of gems. Your task is to reorder the gem intensities to maximize the beauty of the hall. The beauty is achieved by interleaving the smallest and largest intensities in a specific manner.

Formally, let \(a_1, a_2, \dots, a_n\) be the sorted list of intensities (in non-decreasing order). The required order is constructed by taking:

[ \begin{aligned} &result[0] = a_1, \ &result[1] = a_n, \ &result[2] = a_2, \ &result[3] = a_{n-1}, \ &\quad \vdots \end{aligned} ]

If n is odd, the middle element \(a_{\lceil n/2 \rceil}\) is appended at the end. For example, if n = 4 and intensities = [10, 20, 30, 40], one valid answer is [10, 40, 20, 30].

Your program should read from stdin and output the reordered intensities to stdout as a space separated list.

inputFormat

The first line contains an integer n, the number of gems.

The second line contains n space-separated positive integers representing the intensities of the gems.

outputFormat

Output a single line containing the reordered list of gem intensities (space separated) that maximizes the beauty.

4
10 20 30 40

10 40 20 30