#include <bits/stdc++.h>
#include "partition.h"
using namespace std;
int sum;
vector<int> func(vector<pair<int, int>> &v, int d){
    vector<int> res(v.size());
    vector<bool> used(d, 0);
    int suma=0;
    for(int i=0;i<d;i++){
        res[i]=v[i].second;
        suma+=v[i].first;
        used[v[i].second]=true;
    }
    if(suma>=sum/2&&suma-v[d-1].first<sum/2){
        for(int i=d;i<v.size();i++){
            res[i]=v[i].second;
        }
        return res;
    }
    int dr=v.size()-1;
    for(int i=d-1;i>=0&&suma<sum/2;i--){
        suma+=v[dr].second;
        used[res[i]]=false;
        used[v[dr].second]=true;
    }
    if(suma>=sum/2&&suma-v[d].first<sum/2){
        int poz=0;
        for(int i=d;i<v.size();i++){
            while(used[poz])
                poz++;
            res[i]=poz;
            poz++;
        }
        return res;
    }
    res.clear();
    return res;
}
vector<int> solve(std::vector<int> A){
    int N=(int)A.size(), d=0;
    vector<pair<int, int>>v;
    vector<int> res;
    for(int i=0;i<N;i++){
        v.push_back({A[i], i});
        sum+=A[i];
    }
    sort(v.begin(), v.end());
    int l=(N-1)/2, r=N/2;
    while(0<l&&r<=N){
        vector<int> rasp;
        if(l>0){
            rasp=func(v, l);
            if(!rasp.empty())
                return rasp;
            l--;
        }
        if(r<=N){
            rasp=func(v, l);
            if(!rasp.empty())
                return rasp;
            r++;
        }
        l--;
        r++;
    }
    return res;
}
