Consider the following problem:

Input:an array, A, of n sorted integers (positive, negative, or 0) that

A[0] <= A[1] <= A[2] <=A[n-2] <= A[n-1]

Output:re-arrange elements in A such that:

Element at even position (i.e., A[0], A[2]) are less than or equal to both of its neighbors

Element at odd position (i.e., A[1], A[3]) are greater than or equal to both of its neighbors

A[0] <= A[1] >= A[2] <= A[3] >= A[4] <= A[5]

Design an algorithm that solves this problem.

(i) describe the idea behind your algorithm in English;

(ii) provide pseudocode;