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.
}