#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const __int128 maxN = 2e6;
__int128 idx[maxN];

vector<int> solve(vector<int> A) {
    __int128 n = A.size(); __int128 mid = (n - 1) / 2;
    __int128 S = 0;
    for (__int128 x : A) { S += x; }
    __int128 l = 0, r = n - 1;
    for (__int128 i = 0; i < n; i++) {
        if ((__int128)A[i] * n <= S) {
            idx[l++] = i;
        } else {
            idx[r--] = i;
        }
    }
    __int128 sum = 0;
    for (__int128 i = 0; i <= mid; i++) { sum += A[idx[i]]; }
    if (sum * 2 > S) {
        reverse(idx + l, idx + n - l);
        sum = 0;
        for (__int128 i = 0; i <= mid; i++) { sum += A[idx[i]]; }
    }
    vector<int> add, ans;
    add.reserve(n);
    ans.reserve(n);
    __int128 i = 0;
    while (sum * 2 < S) {
        sum += A[idx[n - 1 - i]] - A[idx[i]];
        add.push_back(idx[n - 1 - i]);
        idx[n - 1 - i] = idx[i];
        i++;
    }
    for (; i <= mid; i++) { ans.push_back(idx[i]); }
    for (__int128 x : add) { ans.push_back(x); }
    for (; i < n; i++) { ans.push_back(idx[i]); }
    return ans;
}
