#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<int> solve(vector<int> a) {
    vector<pair<int, int>> x;
    for(int i = 0; i < (int)a.size(); i++) {
        x.push_back({a[i], i});
    }
    sort(x.begin(), x.end());
    sort(a.begin(), a.end());
    vector<int> suff;
    ll sm = 0;
    for(int i = (int)a.size() - 1; i >= 0; i--) {
        sm += a[i];
        suff.push_back(sm);
    }
    int ans = (int)a.size() + 1;
    int tar = sm / 2;
    sm = 0;
    int fst = -1, scn = -1;
    for(int i = 0; i < (int)a.size(); i++) {
        sm += a[i];
        if(sm > tar) {
            int k = i + 1;
            if(ans > abs(((int)a.size() - k) - k)) {
                ans = abs(((int)a.size() - k) - k);
                fst = i;
                scn = -1;
            }
            break;
        }
        int l = 0, r = (int)a.size() - 1, res = -1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(suff[mid] + sm > tar) {
                r = mid - 1;
                res = mid;
            } else {
                l = mid + 1;
            }
        }
        int k = res + 2 + i;
        if(ans > abs(((int)a.size() - k) - k)) {
            ans = abs(((int)a.size() - k) - k);
            fst = i, scn = res;
        }
    }
    vector<int> otv;
    for(int i = 0; i <= fst; i++) {
        otv.push_back(x[i].second);
    }
    for(int i = (int)a.size() - 1; i >= (int)a.size() - 1 - scn; i--) {
        otv.push_back(x[i].second);
    }
    for(int i = fst + 1; i < (int)a.size() - 1 - scn; i++) {
        otv.push_back(x[i].second);
    }
    return otv;

}
