/*
 *      An unbelievably inefficient sorting algorithm
 *
 *      To sort 10 pseudo-random integers:
 *
 *          java SlowSort 10
 */

public class SlowSort {

    static void main (String[] args) {
        int n = (Integer.decode (args[0])).intValue();
        benchmark (n);
    }

    private static void benchmark (int n) {
        SlowSort ss = new SlowSort (n);
        ss.benchmark();
    }

    int[] a;                // array to sort
    int[] sortedarray;      // will become sorted array

    private SlowSort (int n) {
        this.a = testCase (n);
        this.sortedarray = new int[n];
    }

    /*  Returns a test array initialized with pseudo-random data.  */

    private static int[] testCase (int n) {
        int[] a = new int [n];
        for (int i = 0; i < n; i = i + 1)
            a[i] = Math.round ((float) (1000.0 * Math.random ()));
        return a;
    }

    // Copies a sorted version of this.a to this.sortedarray.

    private void sort () {
        nextPermutation (a.length);
    }

    // Generates all permutations of the array a
    // in a grey code order, using Zaks's algorithm.

    private void nextPermutation (int n) {
        if (n > 1) {
            int i = 0;
            while (i < n - 1) {
                nextPermutation (n - 1);
                flip (n);
                i = i + 1;
            }
            nextPermutation (n - 1);
        }
    }

    // Reverses the first n elements of a.

    private void flip (int n) {
        int i = 0;

        // Loop invariant:
        //   0 <= 2 * i <= n
        //   this.a is a permutation of its original contents
        //   during the execution of this call to flip,
        //     a[0] through a[i-1] have been swapped with
        //     a[n-1] through a[n-i].

        // A WHILE LOOP GOES HERE

        checkSorted();
    }

    // Checks to see whether the array a is sorted.
    // If it is, then the sorted array is copied to sortedarray.

    private void checkSorted () {
        boolean ok = true;
        int j = a.length - 1;

        // Loop invariant:
        //   0 <= j < a.length
        //   ok is true if and only if
        //     a[j] through a[a.length - 1] are in sorted order

        // A WHILE LOOP GOES HERE

        if (ok) {
            int n = a.length - 1;

            // Loop invariant:
            //   -1 <= n < a.length
            //   a[n+1] through a[a.length - 1] are equal to
            //     sortedarray[n+1] through sortedarray[a.length - 1]

        // A WHILE LOOP GOES HERE

        }
    }

    // Swaps a[i] with a[j].

    private void swap (int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private void benchmark () {
        int n = a.length;
        int checksum = 0;
        boolean ok = true;
        System.out.print (startMsg);

        for (int i = 0; i < n; i = i + 1)
            checksum = checksum + a[i];

        sort ();

        for (int i = 0; i < n; i = i + 1) {
            checksum = checksum - sortedarray[i];
        }
        for (int i = 1; i < n; i = i + 1) {
            if (sortedarray[i-1] > sortedarray[i])
                ok = false;
            else;
        }

        if (checksum != 0)
            System.out.print (wrongContentsMsg);
        else if (! ok)
            System.out.print (wrongOrderMsg);
        else System.out.print (okMsg);
        System.out.println();

        for (int i = 0; i < n; i = i + 1) {
            System.out.print (sortedarray[i]);
            System.out.print (" ");
        }
        System.out.println();
    }

    static final String startMsg
        = "Slow sort...";
    static final String wrongContentsMsg
        = "failed because the contents are incorrect.";
    static final String wrongOrderMsg
        = "failed because the array is not sorted.";
    static final String okMsg
        = "succeeded.";

}