Ups and Downs

Problem description You will be given a zero-indexed array A. You need to rearrange its elements in such a way that the following conditions are satisfied: - A[i] ≤ A[i+1] if i is even. - A[i] ≥ A[i+1] if i is odd. In other words the following inequality should hold: A[0] ≤ A[1] ≥ A[2] ≤ A[3] ≥ A[4], and so on. Operations ≤ and ≥ should alter. Input The first line contains a single integer T