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

ll getSum(const vector<int>& v, int l, int r) {
    ll ans = 0;
    for (int i = l; i <= r; i++) { ans += v[idx[i]]; }
    return ans;
}

vector<int> solve(vector<int> A) {
    ll n = A.size(); ll mid = (n - 1) / 2;
    ll S = 0;
    for (int x : A) { S += x; }
    int l = 0, r = n - 1;
    for (int i = 0; i < n; i++) {
        if ((ll)A[i] * n <= S) {
            idx[l++] = i;
        } else {
            idx[r--] = i;
        }
    }
    ll sum = getSum(A, 0, mid);
    if (sum * 2 > S) {
        reverse(idx + l, idx + n - l);
        sum = getSum(A, 0, mid);
    }
    vector<int> add, ans;
    int 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++;
        assert(i < n / 2 + 5);
    }
    for (; i <= mid; i++) { ans.push_back(idx[i]); }
    for (int x : add) { ans.push_back(x); }
    for (; i < n; i++) { ans.push_back(idx[i]); }
    return ans;
}
