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

#define pb push_back
#define sz(x) (ll)x.size()
#define pw(x) ((1LL)<<(x))
#define all(x) x.begin(), x.end()

using ll = int;
using ld = long double;

using namespace std;

vector<int> solve(vector<int> A){
    vector<ll> a = A;
    ll n = sz(a);

    ld S=0;
    ll i, j;
    map<ll,vector<ll>> p;
    for (i=0;i<n;i++){
        p[a[i]].pb(i);
        S+=a[i];
    }
    ll flag=0;
    for (auto [_,v] : p){
        if (sz(v)%2!=0) flag = 1;
    }
    if (!flag){
        vector<ll> ans;
        for (auto [_,v] : p){
            for (i=0;i<sz(v)/2;i++) ans.pb(v[i]);
        }
        for (auto [_,v] : p){
            for (i=sz(v)/2;i<sz(v);i++) ans.pb(v[i]);
        }
        return ans;
    }
    ll mn = n+2;
    vector<ll> res;
    for (ll mask=0;mask<pw(n);mask++){
        ll mx=0, mxi=0;
        vector<ll> ans;
        ll kol =__builtin_popcount(mask);
        ld sum=0;
        for (ll i=0;i<n;i++){
            if ((mask>>i)&1){
                if (a[i]>mx){
                    mx = a[i];
                    mxi = i;
                }
                sum+=a[i];
            }
        }
        if (sum>=S/2){

            if (sum-mx<S/2){
                ll r = n-kol;
                if (abs(kol-r)<mn){
                    vector<ll> ans;
                    for (ll i=0;i<n;i++){
                        if ((mask>>i)&1 && i!=mxi){
                            ans.pb(i);
                        }
                    }
                    ans.pb(mxi);
                    for (ll i=0;i<n;i++){
                        if ((mask>>i)%2==0){
                            ans.pb(i);
                        }
                    }
//                cout << sum << " " << S << endl;
                    mn = abs(kol-r);
                    res = ans;
                }
            }
        }
    }
    return res;
}