#include "partition.h"
#include<bitset>
#include<algorithm>
#include<iostream>
#include<utility>
#define all(a) a.begin(),a.end()
using namespace std;
const int N=10000;
int n;
inline pair<bool,bitset<N>> ok(int broi,const vector<int>& A,int kolko,bitset<N> b){
    if((kolko<=0 &&broi==0))return {1,b};
    if(broi==0)return {0,{}};
    for(int i=1;i<=n;++i){
            b[i]=1;
        auto [p,b2]=(ok(broi-1,A,kolko-A[i],b));
        if(p){
            return {1,b2};
        }
            b[i]=0;
    }
    return {0,{}};
}
std::vector<int> solve(std::vector<int> A) {
    n=A.size();
    vector<pair<int,int>> B;
    for(int i=0;i<n;++i)B.push_back({A[i],i});
    sort(all(B),greater<>());
    double s=0;for(auto e:A)s+=e;
    int i=0,j=0,bestToNowRazl=n+2,bestI,bestJ;
    double sum=0;
    while(i<n)
    {
        while(sum<s/2.0 &&j<n)sum+=B[j].first,++j;
        int len=j-i;
        if(abs(len-(n-len))<bestToNowRazl)
        {
            bestI=i,bestJ=j;
            bestToNowRazl=abs(len-(n-len));
        }
      //  cerr<<i<<" "<<j<<endl;
        sum-=B[i].first;
        ++i;
    }
    //cerr<<"While Ended\n";
    vector<int> out;
    //for(int i=bestI;i<bestJ;++i)cerr<<(B[i].first)<<" ";
    //cerr<<endl;
    for(int i=bestI;i<bestJ;++i)out.push_back(B[i].second);
    for(int i=0;i<bestI;++i)out.push_back(B[i].second);
    for(int i=bestJ;i<n;++i)out.push_back(B[i].second);
    return out;
}
