Problem Description:

Write a program that reads ina given array.

- First line of the program will take an integer input N.

- Next line will have Nspace separated integers.

And then outputs a permutation of the array in which the largest element is first, the smallest element is second, the second largest element is third, the second smallest element is fourth, etc. Here, we use a different meaning of second largest comparedtoHW0 (e.g., for array [5 5 4], here the second largest element is 5). Once you find the permuted array, print it to the screen, one element per line.

To solve the problem, use an approach similar to Selection Sort, but instead of always selecting the smallest number, switch between selecting the smallest and the largest number.

Constraints:

- First line: 5 <= N <= 100000

- Next N integers: -100000 <= ni<= 100000

- Usage of any existing Java sorting functions/libraries is not allowed.

- Time complexity should be O(N^2)

Skeleton Code:

// you name here import java.util.*;

public class cmsc401 { private static final Scanner scanner = new Scanner(System.in);

// Please use these methods to take inputs and write outputs. private static Integer readInt() { return scanner.nextInt(); }

private static String readString() { return scanner.next(); }

private static Integer[] readIntegerArray(int size) { Integer[] array = new Integer[size]; for (int i = 0; i < size; i++) { array[i] = readInt(); } return array; }

private static void printInt(int a) { System.out.println(a); }

private static void printString(String s) { System.out.println(s); }

public static void main(String[] args) {

// // reading an Integer // Integer a = readInt(); // // writing int output // printInt(a); // // // reading a String // String s = readString(); // // writing string output // printString(s); // // // reading an Integer Array (you should provide the size) // Integer[] listOfIntegers = readIntegerArray(5);

// write your code here } }