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

long long s_total=0;

vector<int> calc(vector<pair<int, int>> &p, vector<int> &a, int ult)
{
    vector<int> ans(p.size());
    vector<bool> luat(p.size()+1, 0);
    long long sum=0;
    for(int i=0; i<ult; i++)
    {
        ans[i]=p[i].second;
        sum+=p[i].first;
        luat[p[i].second]=1;
    }
    if(sum>=s_total/2 && sum-p[ult-1].first<s_total/2)
    {
        for(int i=ult; i<p.size(); i++)
            ans[i]=p[i].second;
        return ans;
    }
    int dr=p.size()-1;
    for(int i=ult-1; i>=0 && sum<s_total/2; i--)
    {
        sum+=p[dr].first-a[ans[i]];
        luat[ans[i]]=0;
        ans[i]=p[dr].second;
        luat[p[dr].second]=1;
        dr--;
    }
    if(sum>=s_total/2 && sum-p[ult-1].first<s_total/2)
    {
        int poz=0;
        for(int i=ult; i<p.size(); i++)
        {
            while(luat[poz]) poz++;
            ans[i]=poz;
            poz++;
        }
        return ans;
    }
    ans.clear();
    return ans;
}

vector<int> solve(vector<int> a)
{
    int n=a.size();
    s_total=0;
    vector<pair<int, int>> p(n);
    for(int i=0; i<n; i++)
    {
        p[i]={a[i], i};
        s_total+=a[i];
    }
    s_total++;
    sort(p.begin(), p.end());
    int st=(n-1)/2, dr=n/2;
    while(st>0 && dr<=n)
    {
        vector<int> ans;
        if(st>0)
        {
            ans=calc(p, a, st);
            if(!ans.empty()) return ans;
            st--;
        }
        if(dr<=n)
        {
            ans=calc(p, a, dr);
            if(!ans.empty()) return ans;
            dr++;
        }
    }
    return {};
}