using System;

using System.Diagnostics;

​

// Place all distinct values in given array at the beginning.

// (Although keeping other elements were not required,

//  we'll keep the same set of non-distinct elements at the end of array)

public class Program

{

    public static void Main()

    {

        // input

        int n = InputInt("number of elements");

        Trace.Assert(n > 0);

        int [] a = new int[n];

        for(int i = 0; i < a.Length; i++)

        {

            a[i] = InputInt(string.Format("a[{0}]", i));

        }

        int u = 1;

        int s = 0;

        // invariant: a contains same values as on input (possibly in different order) and

        //            first u elements (in a[0..u-1]) are different among each other and

        //            last s elements (in a[a.Length-s..a.Length-1]) have values that already occur in a[0..u-1] and

        //            u + s <= a.Length

        while(u + s != a.Length)

        {

            // check whether a[u] is unique

            int i = 0;

            // invariant: a[u] does not match with any of a[0..i-1] and i <= u)

            while (i != u && a[i] != a[u])

            {

                i++;

            }

            if(i == u)

            {   // a[u] does not match any of a[0..u-1] => a[0..u] are all unique

                u++;    // we have one more unique value

                // first u elements are all distinct

            }   

            else

            {   // a[u] is not unique, and a[a.Length-s..a.Length-1] are not unique, join a[u] there

                // note: since we modify array by swaps only, we guarantee that all original elements are preserved

                swap(ref a[u], ref a[a.Length - s - 1]);

                s++;    // we have one more non-unique element

                // last s elements are already met in a[0..u-1]

            }

        }

        // first u elements are unique and remaining elements are repetitions

        Console.WriteLine("a contains {0} distincs values", u);

        for(int i=0; i < u ; i++)

        {

            Console.WriteLine("a[{0}]={1}", i, a[i]);

        }

        // Complexity:

        // a.Length - (u + s) has been decreased by 1 on each iteration, so the outer loop has exactly a.Length-1 iterations

        // u <= a.Length, so inner loop has a.Length iterations at maximum

        // Thus, the complexity is O((a.Length)**2)

    }

    public static int InputInt(string prompt)

    {

        Console.Write("Enter " + prompt + ": ");

        return Convert.ToInt32(Console.ReadLine());

    }

    public static void swap(ref int a, ref int b)

    {

        int temp = a;

        a = b;

        b = temp;

    }

}