Rearrange Array to Maximize Adjacent Differences

Given an array of integers (A = [a_1, a_2, \dots, a_n]), you are required to rearrange the array elements such that the difference between any two adjacent elements is maximized. In other words, if the rearranged array is (B = [b_1, b_2, \dots, b_n]), you want to maximize the differences (|b_1 - b_2|, |b_2 - b_3|, \dots, |b_{n-1} - b_n|).

The strategy is to sort the array and then select elements alternately from the largest and smallest ends. This guarantees that the differences between successive numbers are as large as possible. Note that multiple answers may exist but you only need to output one valid rearrangement.

inputFormat

The first line contains a single integer (n), the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

Output a single line with (n) space-separated integers representing the rearranged array.## sample

5
1 3 5 2 4

5 1 4 2 3