Rearrange the array with alternate high and low elements

Given an array of integers, rearrange the array such that every second element of the array is greater than its left and right elements. Assume no duplicate elements are present in the array.

Example Solution

Let array arr equal to [ 1, 2, 3, 4, 5, 6, 7 ]. The solution should return the array [ 1, 3, 2, 5, 4, 7, 6 ].