Problem Description

Rearrange an array into a wave form where elements alternate between peaks and valleys: arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4]... You can modify the array in-place.

Input Format

First line contains n (array size). Second line contains n space-separated integers.

Output Format

Array elements rearranged in wave form, space-separated.

Constraints

• 1 ≤ n ≤ 1000

• -1000 ≤ array elements ≤ 1000

• Multiple valid answers possible

• Elements at even indices should be >= neighbors

• Elements at odd indices should be <= neighbors

Sample Input/Output

6
3 6 5 10 7 20

6 3 10 5 20 7

Explanation

The array is rearranged so that: 6>=3, 3<=10, 10>=5, 5<=20, 20>=7. This creates a wave pattern where even-indexed elements are peaks and odd-indexed elements are valleys.