using System;

class Program
{

    static void Partition(int start , int end)
    {
        if(start < end)
        {
            int pivot = arr[start];
            int ii, jj;
            ii = start-1;
            jj = end+1;

            while (ii < jj)
            {
                ii++;
                while(arr[ii] < pivot)
                {
                    ii++;
                }
                jj--;
                while(arr[jj] > pivot)
                {
                    jj--;
                }

                if (ii < jj)
                {
                    int element;
                    element = arr[ii];
                    arr[ii] = arr[jj];
                    arr[jj] = element;
                }
            }
            Partition(start, jj);
            Partition(jj+1, end);
        }
    }

    public static int[] arr;

    static void Main()
    {
        Console.Write("Enter size of the array: ");
        int size = int.Parse(Console.ReadLine());
        arr = new int[size];

        Random rnd = new Random();

        for (int k = 0; k < size; k++)
        {
            arr[k] = rnd.Next(-10,10);
        }

        Partition(0,size-1);

        Console.WriteLine("Sorted array: ");
        for (int i = 0; i < size; i++)
        {
            Console.Write(arr[i] + " ");
        }
        Console.ReadLine();
    }
}