#include "partition.h"
#include <bits/stdc++.h>

using namespace std;


std::vector<int> solve(std::vector<int> A) {
    int n = A.size();
    vector<pair<int,int>> V;
    for(int i=0; i<n; i++) V.push_back({A[i], i});
    sort(V.begin(), V.end());
    sort(A.begin(), A.end());
    vector<int>suf(n+1,0);
    for(int i=n-1; i>=0; i--) {
        suf[i] = suf[i+1]+A[i];
    }
    reverse(suf.begin(), suf.end());
    int S = suf[n];
    int sum=0,Ans=1e9;
    vector<int>ans;
    for(int i=0; i<n; i++) {
        sum += A[i];
        int uzeti = lower_bound(suf.begin(), suf.end(), (S+1)/2 - sum) - suf.begin();
        int TMP=i+uzeti;
        if(abs(TMP-(n-TMP)) < Ans) {
            Ans = abs(TMP-(n-TMP));
            vector<int> v;
            for(int j=0; j<=i; j++) v.push_back(V[j].second);
            for(int j=n-1; j>=n-uzeti; j--) v.push_back(V[j].second);
            for(int j=i+1; j<n-uzeti; j++) v.push_back(V[j].second);
            ans = v;
        }
    }
    return ans;
}
