#include "partition.h"
#include <bits/stdc++.h>
#define abs(x) ((x) < 0 ? -(x) : (x))
#define mkp make_pair

using namespace std;

int n, sum;
vector<int> v, perm;
vector<int> best;
int score;

void tryThis(deque<int> vec) {
    int s = 0;
    for(int i=0; i<n; ++i) {
        s += v[vec[perm[i]]];
        if(s >= (sum + 1) / 2) {
            if(abs(i + 1 - (n - i - 1)) < score) {
                score = abs(i + 1 - (n - i - 1));
                best = vector<int>(vec.begin(), vec.end());
            }
            return;
        }
    }
}

vector<int> solve(vector<int> _v) {
    v = _v;
    n = v.size();
    score = n;
    sum = accumulate(v.begin(), v.end(), 0);
    perm.assign(n, 0);
    for(int i=0; i<n; ++i) {
        perm[i] = i;
    }
    sort(perm.begin(), perm.end(), [](int a, int b){return v[a] > v[b];});
    deque<int> dq;
    for(int i=0; i<n; ++i) {
        dq.push_back(i);
    }
    for(int i=0; i<n; ++i) {
        tryThis(dq);
        dq.push_back(dq.front());
        dq.pop_front();
    }
//    cerr << score << endl;
    for(int &i : best) {
        i = perm[i];
    }
    return best;
}
