#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define x first
#define y second
vector<int> extractSol(deque<ll> first, ll N) {
    vector<int> beg;
    vector<int> end;
    vector<bool> in(N,false);
    while (!first.empty()) {
        in[first.front()] = true;
        first.pop_front();
    }
    for (int i = 0; i < N; i++) {
        if (in[i]) {
            beg.push_back(i);
        } else {
            end.push_back(i);
        }
    }
    for (ll e : end) {
        beg.push_back(e);
    }
    return beg;
}
std::vector<int> solve(std::vector<int> A) {
    ll N = A.size();
    ll S = 0;
    vp B(N);
    for (int i = 0; i < N; i++) {
        S+=A[i];
        B[i] = make_pair(A[i],i);
    }
    sort(B.begin(), B.end());
    deque<ll> I;
    ll sum = 0;
    ll half;
    if (N % 2 == 0) {
        half = N/2;
    } else {
        half = N/2 + 1;
    }
    for (int i = 0; i < half; i++) {
        sum += B[i].x;
        I.push_front(B[i].y);
    }
    ll ind = N - 1;
    ll halfs;
    if (S % 2 == 0) {
        halfs=S/2;
    } else {
        halfs = S/2 + 1;
    }
    while (sum < halfs) {
        sum -= A[I.back()];
        I.pop_back();
        I.push_front(B[ind].y);
        sum += B[ind].x;
    }
    return extractSol(I,N);
}