#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> solve(vector<int> A) {
    vector<pair<long long, int>> v;
    for (int i = 0; i < (int)A.size(); i ++){
        v.push_back({A[i], i});
    }
    sort(v.begin(), v.end(), greater<pair<long long, int>>());
    vector<int> a, b;
    long long cnt1 = 0, cnt2 = 0;
    for (int i = 2; i <= (int)A.size(); i += 2){
        if (cnt2 + v[i].first - (cnt1 + (i != (int)A.size() ? v[i + 1].first : 0)) <= v[1].first){
            b.push_back(v[i].second);
            cnt2 += v[i].first;
            if (i != (int)A.size()){a.push_back(v[i + 1].second); cnt1 += v[i + 1].first;}
        }
        else {
            a.push_back(v[i].second);
            cnt1 += v[i].first;
            if (i != (int)A.size()){b.push_back(v[i + 1].second); cnt2 += v[i + 1].first;}
        }
    }
    a.push_back(v[1].second);
    for (int i : b)a.push_back(i);
    return {a};
}
