#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;
vector<int> best;
int score;
mt19937 mt(67676767);

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

vector<int> solve(vector<int> _v) {
    v = _v;
    n = v.size();
    score = n;
    sum = accumulate(v.begin(), v.end(), 0);
    vector<int> perm;
    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];});
    for(int i=0; i<50; ++i) {
        shuffle(perm.begin(), perm.end(), mt);
        deque<int> dq;
        for(int i=0; i<n; ++i) {
            dq.push_back(i);
        }
        for(int i=0; i<n; ++i) {
            tryThis(dq, perm);
            dq.push_back(dq.front());
            dq.pop_front();
        }
    }
//        cerr << score << endl;
    return best;
}
