#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin() x.end()
#define pb push_back
vector<int> solve(vector<int> a) {
    int n = a.size();
    vector <pair <int, int> > b(n);
    ll sum = 1;
    for (int i = 0; i < n; i++) {
        b[i] = {a[i], i};
        sum += a[i];
    }
    sum /= 2;
    sort(all(b));
    vector <int> id1, id2;
    ll s1 = 0, s2 = 0;
    for (int i = 0; i < n; i++) {
        auto [x, id] = b[i];
        if (i & 1) {
            if (s2 >= sum) {
                id1.pb(id);
                s1 += x;
            } else {
                id2.pb(id);
                s2 += x;
            }
        } else {
            if (s1 >= sum) {
                id2.pb(i);
                s2 += x;
            } else {
                id1.pb(i);
                s1 += x;
            }
        }
    }
    vector <int> ans;
    if (s1 >= sum) {
        for (auto x : id1) ans.pb(x);
        for (auto x : id2) ans.pb(x);
    } else {
        for (auto x : id2) ans.pb(x);
        for (auto x : id1) ans.pb(x);
    }
    return ans;
}
