#include "partition.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

vector<int> mySolve(const vector<int>& A, vector<int>& idx, ll sum, ll S, ll n) {
    vector<int> add;
    add.reserve(n);
    int st = 0, 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];
        st++;
        i++;
    }
    vector<int> ans(n);
    for (i = st; i <= (n - 1) / 2; i++) {
        ans.push_back(idx[i]);
    }
    for (int x : add) { ans.push_back(x); }
    for (int i = (n - 1) / 2 + 1; i < n; i++) {
        ans.push_back(idx[i]);
    }
    return ans;
}

vector<int> solve(vector<int> A) {
    if (A.size() == 1) { return { 0 }; }
    ll n = A.size();
    ll S = 0;
    for (int x : A) { S += x; }
    vector<int> idx(n);
    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;
        }
    }
    int smAvg = l, grAvg = (n - 1 - r);
//    assert(smAvg + grAvg == n);

    ll sum = getSum(A, idx, 0, (n - 1) / 2);
    if (sum * 2 <= S) {
        idx = mySolve(A, idx, sum, S, n);
    } else {
        assert(l <= n / 2 + 1);
        reverse(idx.begin() + l, idx.end() - l);
        sum = getSum(A, idx, 0, (n - 1) / 2);
//        assert((sum - (n % 2) * A[idx[(n - 1) / 2]]) * 2 <= S);
        idx = mySolve(A, idx, sum, S, n);
    }
    return idx;
}
