파도정렬

정렬되지 않은 정수배열이 주어지면, 주어진 배열을 파도형태로 정렬하세요.

배열 arr[0..n-1]을 파도형태로 정렬하는 것은 배열의 각 요소가 arr[0] <= arr[1] >= arr[2] <= arr[3] >= arr[4] <= 형태로 정렬되는 것을 의미합니다.

예제 1

입력

arr = [10, 5, 6, 3, 2, 20, 100, 80]

출력

[2, 10, 3, 20, 5, 80, 6, 100, 10]