#include "partition.h"

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

std::vector<int> solve(std::vector<int> A) {
    int n = A.size();

    vector <int> p(n);

    iota(begin(p), end(p), 0);
    sort(begin(p), end(p), [&](int &i, int &j){
         return A[i] < A[j];
    });

    deque <int> L, R;

    i64 S = 0, x = 0;

    for ( int i = 0; i < n; i++ ){
        if ( i < (n + 1) / 2 ) L.push_back(p[i]), x += A[p[i]];
        else R.push_back(p[i]);

        S += A[p[i]];
    }

    S = (S + 1) / 2;

    while ( x < S ){
        x += A[R.back()] - A[L.front()];

        R.push_front(L.front());
        L.push_back(R.back());

        L.pop_front(), R.pop_back();
    }

    vector <int> ans;

    for ( auto &x: L ) ans.push_back(x);
    for ( auto &y: R ) ans.push_back(y);

    return ans;
}
