#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
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){
    return Brute(A);
    /*int n=A.size();
    vector<pair<int,int>>a;
    for(int i=0;i<n;i++)a.pb({A[i],i});
    sort(a.begin(),a.end());
    reverse(a.begin()+n/2,a.end());
    ll S=0;
    for(auto i:A)S+=i;
    vector<pair<int,int>>x;
    for(ll i=0,sum=0;i<n;i++)if(sum*2<S){
        x.pb(a[i]);
        sum+=a[i].fi;
    }
    sort(x.begin(),x.end());
    reverse(x.begin(),x.end());
    while(x.size()>n/2){
        x.pop_back();
    }
    ll sum=0;
    for(auto [a,b]:x)sum+=a;
    vector<int>res;
    reverse(x.begin(),x.end());
    int was[n+5]={0};
    for(auto [a,b]:x)was[b]=true;
    vector<pair<int,int>>y;
    for(int i=0;i<n;i++)if(!was[i])y.pb({A[i],i});
    sort(y.begin(),y.end());
    if(sum*2>=S){
        for(auto [a,b]:x)res.pb(b);
        for(auto [a,b]:y)res.pb(b);
    }
    else{
        for(auto [a,b]:y)res.pb(b);
        for(auto [a,b]:x)res.pb(b);
    }
    return res;*/
}
