#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> solve(vector<int> A)
{
    vector<pair<int,int>> v;
    ll s=0;
    for(int i=0;i<A.size();i++)
    {
        s+=A[i];
        v.push_back({A[i],i});
    }
    sort(v.begin(),v.end());
    int n=v.size();
    int pref[n+1];
    int pref1[n+1];
    pref[0]=0;
    pref1[n]=0;
    set<pair<int,int>> st2;
    st2.insert({0,0});
    for(int i=1;i<n;i++)
    {
        pref[i]=pref[i-1]+v[i-1].first;
    }
    for(int i=n-1;i>=0;i--)
    {
        pref1[i]=pref1[i+1]+v[i].first;
        st2.insert({pref1[i],n-i});
    }
    int goal=(s+1)/2;
    int minn=n;
    for(int i=0;i<=n;i++)
    {
        auto x=st2.lower_bound({goal-pref[i],0});
        auto y=*x;
        minn=min(minn,abs(n-2*i-2*y.second));
    }
    vector<int> ans;
    for(int i=0;i<=n;i++)
    {
        auto x=st2.lower_bound({goal-pref[i],0});
        auto y=*x;
        if(minn==abs(n-2*i-2*y.second))
        {
            for(int j=0;j<i;j++)
            {
                ans.push_back(v[j].second);
            }
            for(int j=n-1;j>=n-y.second;j--)
            {
                ans.push_back(v[j].second);
            }
            for(int j=i;j<n-y.second;j++)
            {
                ans.push_back(v[j].second);
            }
            return ans;
        }
    }
}
