import java.io.*;

// Quick Sort implementation using a pivot-based partition strategy
class QuickSort {
    int[] array;    // The array to be sorted
    int lowerBound; // Starting index (0-based)
    int upperBound; // Ending index (array.length - 1)
    int size;       // Total number of elements

    public QuickSort(int[] inputArray) {
        array = inputArray;
        lowerBound = 0;
        size = array.length;
        upperBound = array.length - 1;
    }

    // Public entry point: starts the sort across the full array
    public void sort() {
        sortPartition(lowerBound, upperBound);
    }

    // Recursively sorts the subarray between indices lb and ub
    private void sortPartition(int lb, int ub) {
        if (lb >= ub) return;  // Base case: nothing to sort

        int[] temp = new int[size];
        int tempIndex = lb;
        int pivot = array[lb];  // Choose first element as pivot

        if (lb == ub) {
            temp[lb] = pivot;
            return;
        }

        // Phase 1: elements smaller than pivot go to left side of temp
        for (int i = lb; i <= ub; i++) {
            if (pivot > array[i]) {
                temp[tempIndex] = array[i];
                tempIndex++;
            }
        }

        // Phase 2: pivot goes in its correct sorted position
        int pivotIndex = tempIndex;
        temp[tempIndex] = pivot;
        tempIndex++;

        // Phase 3: elements larger than pivot go to right side
        for (int i = lb; i <= ub; i++) {
            if (pivot < array[i]) {
                temp[tempIndex] = array[i];
                tempIndex++;
            }
        }

        // Copy rearranged section back into original array
        for (int i = lb; i <= ub; i++) {
            array[i] = temp[i];
        }

        // Recursively sort left and right partitions
        if (lb < ub) {
            sortPartition(lb, pivotIndex - 1);
            sortPartition(pivotIndex + 1, ub);
        }
    }

    // Prints all elements of the array separated by spaces
    public void display() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

public class QuickSortDemo {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        System.out.print("Enter the size of array: ");
        int size = Integer.parseInt(reader.readLine());

        int[] array = new int[size];
        System.out.println("Enter " + size + " elements (one per line):");
        for (int i = 0; i < size; i++) {
            array[i] = Integer.parseInt(reader.readLine());
        }

        QuickSort sorter = new QuickSort(array);

        System.out.print("Array before sort: ");
        sorter.display();

        sorter.sort();

        System.out.print("Array after sort:  ");
        sorter.display();
    }
}