using System;
using System.Diagnostics;

public class Chall2
{

    public static void Main(string[] args)
    {
        int max = int.Parse(args[0]);
        var rand = new Random();
        Stopwatch sw = new Stopwatch();
        sw.Start();

        var result = Shuffle( max, n=> rand.Next(n+1) );
        sw.Stop();

        Console.WriteLine(" In : {0} ms", sw.Elapsed.TotalMilliseconds);

    }


    // n: number of slots (shuffles n-1)
    // generator:  a random generator given x that gives 0 <= val <= x
    private static int[] Shuffle(int n, Func<int, int> generator)
    {
        int[] values = new int[n];
        values[0] = 0;
        for( int i=1; i < n; i++)
        {
            var pick = generator(i);
            values[i] = values[pick];
            values[pick] = i;
        }
        return values;
    }

    //proof by induction:  Each number is output once, and
    // for each possible sequence of random numbers,
    // a different output sequence is obtained
    //   For n = 2:
    //  Possible random sequence:     Output:
    //          0                       [1,0]
    //          1                       [0,1]
    //   For n =3
    //          0, 0                    [2,0,1]
    //          0, 1                    [1,0,2]
    //          1, 0                    [0,1,2]
    //          1, 1                    [0,2,1]
    //          0, 2                    [1,2,0]
    //      and so on... (left to the reader)
    // Since there are n! possible random sequences, and
    // n! possible shuffles, and each unique random sequence
    // outputs a unique shuffle, every possible shuffle has
    // an equal chance, given an acceptable random generator.
}