Zigzag Array Rearrangement

Given an integer n and an array of n integers, rearrange the array into a zigzag order. First, sort the array in ascending order, then construct a new array by alternately choosing the smallest and largest remaining elements. This process continues until all elements are used.

For example, if n = 5 and the array is [4, 1, 3, 2, 5], after sorting it becomes [1, 2, 3, 4, 5] and the zigzag arrangement is [1, 5, 2, 4, 3].

inputFormat

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

outputFormat

Output a single line containing the zigzag arranged array. The elements must be separated by a single space.

5
4 1 3 2 5

1 5 2 4 3