using System; using System.Text;
using System.Text.RegularExpressions;
 
public static class ThanosMeanLessMemory
{   // --- int[] ---
    public static void ThanosIntSortInPlace(int[] a)
    {   if (a == null || a.Length < 2) return;
        var sorted = SortNoExtraCopy(a);
        Array.Copy(sorted, a, a.Length);
    }
 
    private static int[] SortNoExtraCopy(int[] seg)
    {   int n = seg.Length;
        if (n < 2) return seg;
 
        int mn = seg[0], mx = seg[0]; long sum = seg[0];
        for (int i = 1; i < n; i++) { int v = seg[i]; if (v < mn) mn = v; if (v > mx) mx = v; sum += v; }
        if (mn == mx) return seg;
 
        double c = sum / (double)n;
 
        int cntL = 0; foreach (var v in seg) if (v <= c) cntL++;
        int cntR = n - cntL;
 
        var left = new int[cntL];
        var right = new int[cntR];
        int iL = 0, iR = 0;
        foreach (var v in seg) if (v <= c) left[iL++] = v; else right[iR++] = v;
 
        left = SortNoExtraCopy(left);
        right = SortNoExtraCopy(right);
 
        var outArr = new int[n];
        Array.Copy(left, 0, outArr, 0, left.Length);
        Array.Copy(right, 0, outArr, left.Length, right.Length);
        return outArr;
    }
 
    // --- генераторы ---
 
    public static int[] GenerateRandomArray(int n, int min, int max)
    {   var rnd = new Random();
        var arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = rnd.Next(min, max + 1);
        return arr;
    }
}
 
public class Program
{   static string Arr<T>(T[] a) => "[" + string.Join(", ", a) + "]";
 
    public static void Main()
    {   // Консоль в UTF-8
        Console.OutputEncoding = Encoding.UTF8;
        Console.InputEncoding = Encoding.UTF8;
 
        // int
        var x = new[] { 5, 1, 9, 3, 7, 2, 2, 8, 4, 6 };
        ThanosMeanLessMemory.ThanosIntSortInPlace(x);
        Console.WriteLine(Arr(x));
 
        var arr = ThanosMeanLessMemory.GenerateRandomArray(25, -1000, 1000);
        Console.WriteLine("arr  before : " + Arr(arr));
        ThanosMeanLessMemory.ThanosIntSortInPlace(arr);
        Console.WriteLine("arr  sorted : " + Arr(arr));
}}

dXNpbmcgU3lzdGVtOyB1c2luZyBTeXN0ZW0uVGV4dDsKdXNpbmcgU3lzdGVtLlRleHQuUmVndWxhckV4cHJlc3Npb25zOwogCnB1YmxpYyBzdGF0aWMgY2xhc3MgVGhhbm9zTWVhbkxlc3NNZW1vcnkKeyAgIC8vIC0tLSBpbnRbXSAtLS0KICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBUaGFub3NJbnRTb3J0SW5QbGFjZShpbnRbXSBhKQogICAgeyAgIGlmIChhID09IG51bGwgfHwgYS5MZW5ndGggPCAyKSByZXR1cm47CiAgICAgICAgdmFyIHNvcnRlZCA9IFNvcnROb0V4dHJhQ29weShhKTsKICAgICAgICBBcnJheS5Db3B5KHNvcnRlZCwgYSwgYS5MZW5ndGgpOwogICAgfQogCiAgICBwcml2YXRlIHN0YXRpYyBpbnRbXSBTb3J0Tm9FeHRyYUNvcHkoaW50W10gc2VnKQogICAgeyAgIGludCBuID0gc2VnLkxlbmd0aDsKICAgICAgICBpZiAobiA8IDIpIHJldHVybiBzZWc7CiAKICAgICAgICBpbnQgbW4gPSBzZWdbMF0sIG14ID0gc2VnWzBdOyBsb25nIHN1bSA9IHNlZ1swXTsKICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8IG47IGkrKykgeyBpbnQgdiA9IHNlZ1tpXTsgaWYgKHYgPCBtbikgbW4gPSB2OyBpZiAodiA+IG14KSBteCA9IHY7IHN1bSArPSB2OyB9CiAgICAgICAgaWYgKG1uID09IG14KSByZXR1cm4gc2VnOwogCiAgICAgICAgZG91YmxlIGMgPSBzdW0gLyAoZG91YmxlKW47CiAKICAgICAgICBpbnQgY250TCA9IDA7IGZvcmVhY2ggKHZhciB2IGluIHNlZykgaWYgKHYgPD0gYykgY250TCsrOwogICAgICAgIGludCBjbnRSID0gbiAtIGNudEw7CiAKICAgICAgICB2YXIgbGVmdCA9IG5ldyBpbnRbY250TF07CiAgICAgICAgdmFyIHJpZ2h0ID0gbmV3IGludFtjbnRSXTsKICAgICAgICBpbnQgaUwgPSAwLCBpUiA9IDA7CiAgICAgICAgZm9yZWFjaCAodmFyIHYgaW4gc2VnKSBpZiAodiA8PSBjKSBsZWZ0W2lMKytdID0gdjsgZWxzZSByaWdodFtpUisrXSA9IHY7CiAKICAgICAgICBsZWZ0ID0gU29ydE5vRXh0cmFDb3B5KGxlZnQpOwogICAgICAgIHJpZ2h0ID0gU29ydE5vRXh0cmFDb3B5KHJpZ2h0KTsKIAogICAgICAgIHZhciBvdXRBcnIgPSBuZXcgaW50W25dOwogICAgICAgIEFycmF5LkNvcHkobGVmdCwgMCwgb3V0QXJyLCAwLCBsZWZ0Lkxlbmd0aCk7CiAgICAgICAgQXJyYXkuQ29weShyaWdodCwgMCwgb3V0QXJyLCBsZWZ0Lkxlbmd0aCwgcmlnaHQuTGVuZ3RoKTsKICAgICAgICByZXR1cm4gb3V0QXJyOwogICAgfQogCiAgICAvLyAtLS0g0LPQtdC90LXRgNCw0YLQvtGA0YsgLS0tCiAKICAgIHB1YmxpYyBzdGF0aWMgaW50W10gR2VuZXJhdGVSYW5kb21BcnJheShpbnQgbiwgaW50IG1pbiwgaW50IG1heCkKICAgIHsgICB2YXIgcm5kID0gbmV3IFJhbmRvbSgpOwogICAgICAgIHZhciBhcnIgPSBuZXcgaW50W25dOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSBhcnJbaV0gPSBybmQuTmV4dChtaW4sIG1heCArIDEpOwogICAgICAgIHJldHVybiBhcnI7CiAgICB9Cn0KIApwdWJsaWMgY2xhc3MgUHJvZ3JhbQp7ICAgc3RhdGljIHN0cmluZyBBcnI8VD4oVFtdIGEpID0+ICJbIiArIHN0cmluZy5Kb2luKCIsICIsIGEpICsgIl0iOwogCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgTWFpbigpCiAgICB7ICAgLy8g0JrQvtC90YHQvtC70Ywg0LIgVVRGLTgKICAgICAgICBDb25zb2xlLk91dHB1dEVuY29kaW5nID0gRW5jb2RpbmcuVVRGODsKICAgICAgICBDb25zb2xlLklucHV0RW5jb2RpbmcgPSBFbmNvZGluZy5VVEY4OwogCiAgICAgICAgLy8gaW50CiAgICAgICAgdmFyIHggPSBuZXdbXSB7IDUsIDEsIDksIDMsIDcsIDIsIDIsIDgsIDQsIDYgfTsKICAgICAgICBUaGFub3NNZWFuTGVzc01lbW9yeS5UaGFub3NJbnRTb3J0SW5QbGFjZSh4KTsKICAgICAgICBDb25zb2xlLldyaXRlTGluZShBcnIoeCkpOwogCiAgICAgICAgdmFyIGFyciA9IFRoYW5vc01lYW5MZXNzTWVtb3J5LkdlbmVyYXRlUmFuZG9tQXJyYXkoMjUsIC0xMDAwLCAxMDAwKTsKICAgICAgICBDb25zb2xlLldyaXRlTGluZSgiYXJyICBiZWZvcmUgOiAiICsgQXJyKGFycikpOwogICAgICAgIFRoYW5vc01lYW5MZXNzTWVtb3J5LlRoYW5vc0ludFNvcnRJblBsYWNlKGFycik7CiAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoImFyciAgc29ydGVkIDogIiArIEFycihhcnIpKTsKfX0=