#include "partition.h"
#define _GLIBCXX_FILESYSTEM
#include<bits/stdc++.h>
using namespace std;
vector<int> solve(vector<int> a) {
    vector<pair<int, int>> aiidx;
    int s = 0, s1 = 0, s2 = 0;
    for (int i = 0; i < a.size(); i++) {
        aiidx.push_back({a[i], i});
        s+=a[i];
    }
    sort(aiidx.begin(), aiidx.end());
    reverse(aiidx.begin(), aiidx.end());
    vector<int> m;
    vector<int> d;
    for (int i = 0; i < aiidx.size(); i++) {
        if (s1+aiidx[i].first < (s+1)/2) {
            m.push_back(aiidx[i].second);
            s1+=aiidx[i].first;
            continue;
        }
        if (s2+aiidx[i].first < (s+1)/2) {
            d.push_back(aiidx[i].second);
            s2+=aiidx[i].first;
            continue;
        }
        for (int j = i+1; j < aiidx.size(); j++) {
            if (m.size() < d.size()) m.push_back(aiidx[j].second);
            else d.push_back(aiidx[j].second);
        }
        m.push_back(aiidx[i].second);
    }
    for (int i = 0; i < d.size(); i++) m.push_back(d[i]);
    return m;
}
