using System;

​

// 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()

    {

        int [] a = { 1, 1, 6, 5, 4, 3, 4, 6, 1, 7, 2, 1, 4, 9};

        int N = a.Length; // just an abbreviation for readability

        Array.Sort(a);

        int u = 1;

        int s = 0;

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

        //            first u elements are unique: a[0]<..<a[u-1] and 

        //            next s elements (a[u..u+s-1]) already occur in a[0..u-1]

        //            remaining elements go in non-descending order: a[u-1]<=a[u+s]<=..<=a[N-1] and

        //            u > 0 and 

        //            u + s <= N

        while(u + s != N)

        {

            // check whether a[u] is unique

            if(a[u+s]!=a[u-1])  // => a[u-1]<a[u+s]

            {   // a[u+s] does not match any of a[0..u-1], append it to a[0..u-1] segment

                swap(ref a[u], ref a[u+s]);

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

                // first u elements are all distinct

            }   

            else

            {   // a[u+s] is not unique, so it extends the segment of non-unique elements

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

                // last a[u..u+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);

        print(a, u);

        // Complexity:

        // sorting takes N log N

        // while loop has N iterations

        // Thus, the complexity is O(N * log N) + O(N) = O(N * log N)

        // Side note: the order of repeating elements (a[u .. N-1]) is unpredictable

        // but we always can sort these anyway we want within the same time constraint

    }

    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;

    }

    public static void print(int[] a, int n)

    {

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

        {

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

        }

    }

}