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

using namespace std;

int n;
vector<int> v;
vector<vector<pair<int, pair<int, int>>>> dp;

bool comp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    return abs(a.first) < abs(b.first) || abs(a.first) == abs(b.first) && a.first > b.first;
}

vector<int> solve(vector<int> _v) {
    v = _v;
    n = v.size();
    dp.resize(n + 1);
    dp[0] = {{0, {0, 0}}};
    for(int i=1; i<=n; ++i) {
        int x = v[i-1];
        for(int j = 0; j < dp[i-1].size(); ++j) {
            auto [val, idx] = dp[i-1][j];
            dp[i].emplace_back(val + x, mkp(i-1, j));
            dp[i].emplace_back(val - x, mkp(i-1, j));
        }
        sort(dp[i].begin(), dp[i].end(), comp);
        dp[i].erase(unique(dp[i].begin(), dp[i].end(), comp), dp[i].end());
        dp[i].resize(min((int)dp[i].size(), 10));
    }
//    cerr << dp[n][0].first << endl;
    int pos = n, idx = 0;
    vector<int> l1, l2;
    while(pos != 0) {
        auto [val, p] = dp[pos][idx];
        if(val > dp[p.first][p.second].first) {
            l1.push_back(pos - 1);
        } else {
            l2.push_back(pos - 1);
        }
        pos = p.first;
        idx = p.second;
    }
    for(int i : l2) {
        l1.push_back(i);
    }
    return l1;
}
