Taco Snake Pattern

In this problem, you are given an array of integers and you need to rearrange the array into a snake pattern. In the snake pattern, for any index (i) where (0 \le i < n-1):

• If (i) is even, then (a_i \le a_{i+1})
• If (i) is odd, then (a_i \ge a_{i+1})

You need to modify the given array in-place such that it satisfies the above conditions. For example, given an array [3, 1, 2, 5, 4] with (n = 5), the resulting snake pattern should be [1, 3, 2, 5, 4].

inputFormat

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

outputFormat

Print the rearranged array in snake pattern as a single line of space-separated integers.## sample

5
3 1 2 5 4

1 3 2 5 4