#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
int Calc(vector<int>A,vector<int>res){
    ll S=0;for(auto i:A)S+=i;
    ll sum=0;int cnt1=0,cnt2=A.size();
    for(auto i:res)if(sum*2<S){
        sum+=A[i];
        cnt1++;cnt2--;
    }
    return abs(cnt1-cnt2);
}
vector<int>Brute(vector<int>A){
    int n=A.size();
    ll S=0;for(auto i:A)S+=i;
    int ans=1e9;
    vector<int>res;
    for(int mask=1;mask<1<<n;mask++){
        bool moze=true;
        vector<pair<int,int>>x,y;
        for(int i=0;i<n;i++){
            if(mask>>i&1)x.pb({A[i],i});
            else y.pb({A[i],i});
        }
        sort(x.begin(),x.end());
        sort(y.begin(),y.end());
        ll sum=0;
        for(int i=0;i+1<x.size();i++)sum+=x[i].fi;
        if(sum*2>=S)moze=false;
        sum+=x.back().fi;
        if(sum*2<S)moze=false;
        if(moze){
            if(abs((int)x.size()-(int)y.size())<ans){
                ans=abs((int)x.size()-(int)y.size());
                res.clear();
                for(auto i:x)res.pb(i.se);
                for(auto i:y)res.pb(i.se);
            }
        }
    }
    return res;
}
vector<int>solve(vector<int>A){
    int n=A.size();
    vector<int>a,b;
    for(int i=0;i<n/2;i++)a.pb(i);
    for(int i=n/2;i<n;i++)b.pb(i);
    ll sum1=0,sum2=0;
    for(auto i:a)sum1+=A[i];
    for(auto i:b)sum2+=A[i];
    if(sum1<sum2)swap(a,b),swap(sum1,sum2);
    for(int i=0;i<max(a.size(),b.size());i++){
        if(i==max(a.size(),b.size())&&a.size()!=b.size()){
            if(a.size()>b.size()){
                sum1-=a.back();
                sum2+=a.back();
                b.pb(a.back());
                a.pop_back();
            }
            else{
                sum1+=b.back();
                sum2-=b.back();
                a.pb(b.back());
                b.pop_back();
            }
            break;
        }
        sum1-=A[a[i]];
        sum2-=A[b[i]];
        swap(a[i],b[i]);
        sum1+=A[a[i]];
        sum2+=A[b[i]];
        if(sum1<=sum2){
            swap(b[i],b.back());
            break;
        }
    }
    vector<int>res;
    for(auto i:b)res.pb(i);
    for(auto i:a)res.pb(i);
    return res;
}
