#include <bits/stdc++.h>
#include "partition.h"

using namespace std;

vector<int> solve(vector<int> B)
{
    long long i,suma,ind,s,init,N,sol1,sol2,cnt,mini;
    vector<pair<int,int>> A;
    vector<int> ans;
    for(i=0;i<B.size();i++)
    {
        A.push_back({B[i],i});
    }
    sort(A.begin(),A.end());
    N=B.size();
    suma=0;
    for(auto x:B)
        suma+=x;

    init=s=0;
    while(init<N && 2*(s+A[init].first)<suma)
    {
        s+=A[init].first;
        init++;
    }

    sol1=-1;
    s=0;
    i=N-1;
    while(i>=0 && 2*(s+A[i].first)<suma)
    {
        s+=A[i].first;
        i--;
    }
    ind=sol2=i;
    mini=N-i;


    for(i=0;i<=init;i++)
    {
        if(ind==i)
        {
            s-=A[i].first;
            ind++;
        }
        s+=A[i].first;
        while(ind<N && 2*s>=suma && 2*(s-A[ind].first)>=suma)
        {
            s-=A[ind].first;
            ind++;
        }
        cnt=i+1+(N-ind);
        if(abs(2*cnt-N)<abs(2*mini-N))
        {
            mini=cnt;
            sol1=i;
            sol2=ind;
        }
    }
    for(i=0;i<=sol1;i++)
        ans.push_back(A[i].second);
    for(i=sol2;i<N;i++)
        ans.push_back(A[i].second);
    for(i=sol1+1;i<sol2;i++)
        ans.push_back(A[i].second);
    return ans;
}
/*
3
4
1 2 4 8
9
5 6 6 3 1 1 4 4 3
8
2 2 3 2 3 2 2 3
*/
