#include "partition.h"
#include <algorithm>
#include <iostream>
#pragma GCC optimize ("Ofast")
using namespace std;
const int MAXN=2e6+5;
int a[MAXN];
int n;
struct el
{
    int v,i;
};
inline int ga(int len)
{
    return abs(len-(n-len));
}
bool l=1;
std::vector<int> solve(std::vector<int> A)
{
    if(l)
    {
        cout.tie(NULL);
        l=0;
    }
    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;
    }
    long pref=0,sufx=s;
    int bp=-1,bs=-1,d=n+50;
    int p=1;
    long lim=s/2+s%2;
    a[0]=0;
    for(int i=0; i<=n; i++)
    {
        pref+=a[i];
        while(p<=n&&((pref+sufx-a[p])>=lim))
        {
            sufx-=a[p];
            p++;
        }
        int ans=ga(i+(n-p+1));
        if(ans<d)
        {
            bp=i;
            bs=p;
            d=ans;
        }
        if(pref>=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;
}
