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.
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 ]
.