#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;
}

void mySolve(const vector<int>& A, vector<int>& idx, ll sum, ll S, ll n) {
    int i = 0;
    while (sum * 2 < S) {
        sum += A[idx[n - 1 - i]] - A[idx[i]];
        swap(idx[i], idx[n - 1 - i]);
        i++;
    }
    reverse(idx.begin(), idx.begin() + (n - 1) / 2 + 1);
}

vector<int> solve(vector<int> A) {
    ll n = A.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    ll S = getSum(A, idx, 0, n - 1);

    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) {
        mySolve(A, idx, sum, S, n);
    } else {
//        for (int i = 0; i < n; i++) { cout << A[idx[i]] << ' '; }
//        cout << "\nAvg: " << double(S) / n << '\n';
        for (int i = 0; i < l; i++) {
            swap(idx[i], idx[n - 1 - i]);
        }
        reverse(idx.begin(), idx.end());
        sum = getSum(A, idx, 0, (n - 1) / 2);
        assert(sum * 2 <= S);
        mySolve(A, idx, sum, S, n);
    }
    return idx;
}
