Let's say that an array is max-min sorted if the first element of the array is the maximum element, the second is the minimum, the third is the second maximum and so on. Modify Selection sort such that it can be used for max-min sorting.

Input: the first line contains a number nn — the length of an input array. The next line contains nn numbers — the elements of the array.

Output: a max-min sorted input array.

Sample Input 1:

5
1 2 3 4 5

Sample Output 1:

5 1 4 2 3

Sample Input 2:

6
3 1 2 5 4 7

Sample Output 2:

7 1 5 2 4 3

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        int[] array = Arrays.stream(scanner.nextLine().split("\\s+"))
            .limit(n)
            .mapToInt(Integer :: parseInt)
            .toArray();
        Arrays.stream(selectionSort(array)).forEach(i -> System.out.print(i + " "));
    }

    private static int[] selectionSort(int[] array) {

        boolean forMax = true;
        for (int i = 0; i < array.length - 1; i++) {
            int index = i;
            for (int j = i + 1; j < array.length; j++) {
                if (forMax ? array[index] < array[j] : array[index] > array[j]) {
                    index = j;
                }
            }
            forMax = !forMax;
            int temp = array[index];
            array[index] = array[i];
            array[i] = temp;

        }
        return array;
    }
}