#include <bits/stdc++.h>
#include "partition.h"
using namespace std;
int n;
static inline int Dif(int cut) {
    return abs(cut - (n - cut));
}
vector<int> solve(vector<int> a) {
    vector<int> perm;
    map<long long, int> d;
    map<long long, long long> ant, fol;
    n = a.size();
    d[0] = 0;

    long long tot = 0;
    for(int i = 0; i < n; i++) tot += (long long)a[i];

    for(int i = 0; i < n; i++) {
        for(auto it = d.rbegin(); it != d.rend(); it++) {
            if(Dif(d[it->first + a[i]]) > Dif(d[it->first] + 1)) {
                int _x = it->first + a[i];
                  d[it->first + a[i]] = 1 + d[it->first];
                ant[it->first + a[i]] = it->first;
                fol[it->first + a[i]] = i;
                //cout << _x << ' ';
            }
        }
    }
    //cout << '\n';

    //for(auto cur : ant) cout << cur.first << ' ' << cur.second << '\n';

    int difMi = n;
    long long rasp = 0;
    auto it = d.lower_bound(tot / 2 + tot % 2);
    while(it != d.end()) {
        int dif = Dif(it->second);
        if(difMi > dif) {
            difMi = dif;
            rasp = it->first;
        }
        it++;
    }
    //cout << difMi << '\n';

    vector<bool> luat(n, false);

    while(0 != rasp) {
        perm.push_back(fol[rasp]);
        luat[fol[rasp]] = true;
        int _x = fol[rasp];
        rasp = ant[rasp];
    }
    for(int i = 0; i < n; i++) {
        if(!luat[i]) perm.push_back(i);
    }

    return perm;
}
