// RUSSIAN SORTING HALVES DANILIN
using System; using System.Text;
class rsh
{   static long[] a; static long[] d;
    static void Main(string[] args)
    {   int n = 1000000;
        var age = 1 + Math.Log(n) / Math.Log(2);
        Console.WriteLine(n);

        a = new long[n + 1]; d = new long[n + 1];

        var rand = new Random();
        for (int i = 1; i <= n; i++)
            d[i] = rand.Next(1, n);

        // WRITE ON SCREEN
        int m = Math.Min(n, 10);
        for (int i = 1; i <= m; i++)
            Console.Write("{0} ", d[i]);
        Console.WriteLine();

        // RUSSIAN SORTING HALVES DANILIN
        var start = DateTime.Now;
        if (age > 0)
            dav(1, n, 1, age);
        var finish = DateTime.Now;

        Console.WriteLine("{0} second", (finish - start).TotalSeconds);

        // WRITE ON SCREEN
        Console.WriteLine("[1..{0}]", m);
        for (int i = 1; i <= m; i++)
            Console.Write("{0} ", d[i]);
        Console.WriteLine();

        // WRITE ON SCREEN
        Console.WriteLine("[{0}..{1}]", n - m + 1, n);
        for (int i = n - m + 1; i <= n; i++)
            Console.Write("{0} ", d[i]);
        Console.WriteLine();
        Console.WriteLine("Press any key"); Console.ReadKey();
    }

    static void dav(int ab, int yz, int part, double age)
    {   if (yz - ab < 1) return;

        long summa = 0;
        for (int i = ab; i <= yz; i++)
            summa = summa + d[i];

           double middle = summa / (yz - ab + 1.0);
           var abc = ab - 1; var xyz = yz + 1;

        for (int i = ab; i <= yz; i++)
            if (d[i] < middle)
            {   abc = abc + 1; a[abc] = d[i];
            }
            else
            {   xyz = xyz - 1; a[xyz] = d[i];
            }

        for (int i = ab; i <= yz; i++)
            d[i] = a[i];

        if (part < age)
        {   if (abc >= ab) dav(ab, abc, part + 1, age);
            if (xyz <= yz) dav(xyz, yz, part + 1, age);
        }
return; }}