#include "partition.h"
#include <algorithm>
using namespace std;
const int MAXN=2e6+5;
int a[MAXN];
long pref[MAXN];
long sufx[MAXN];
int n;
struct el
{
    int v;
    int i;
    inline bool operator<(const el&x)const
    {
        return v<x.v;
    }
};
inline int ga(int len)
{
    return abs(len-(n-len));
}
std::vector<int> solve(std::vector<int> A)
{
    n=A.size();
    long s=0;
    vector<el> b;b.reserve(n);
    for(int i=0; i<n; i++)
    {
        s+=A[i];
        b.push_back({A[i],i});
    }
    sort(b.begin(),b.end());
    for(int i=0; i<n; i++)
    {
        a[i+1]=b[i].v;
    }
    pref[0]=0;
    for(int i=1; i<=n; i++)
    {
        pref[i]=pref[i-1]+a[i];
    }
    sufx[n+1]=0;
    for(int i=n; i>=1; i--)
    {
        sufx[i]=sufx[i+1]+a[i];
    }
    int bp=-1,bs=-1,d=n+50;
    int p=1;
    long lim=s/2+s%2;
    for(int i=0; i<=n; i++)
    {
        while(p<=i)p++;
        while(p<=n&&((pref[i]+sufx[p+1])>=lim))p++;
        int ans=ga(i+(n-p+1));
        if(ans<d)
        {
            bp=i;
            bs=p;
            d=ans;
        }
        if(pref[i]>=lim)
        {
            break;
        }
    }
    vector<int> ans;ans.reserve(n);
    for(int i=1; i<=bp; i++)
    {
        ans.push_back(b[i-1].i);
    }
    for(int i=n; i>=bs; i--)
    {
        ans.push_back(b[i-1].i);
    }
    for(int i=bp+1; i<=bs-1; i++)
    {
        ans.push_back(b[i-1].i);
    }
    return ans;
}
