#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> solve(std::vector<int> a) {
    vector<pair<int,int>>v;
    vector<int>ans;
    int n = a.size() ;
    for ( int i = 0 ; i < n ; ++ i ) v.push_back(make_pair(a[i],i));
    int o = n ;
    int suma = 0 ;
    for ( int i = 0 ; i < n; ++ i ) suma += a[i] ;
    int suma1 = 0 ;
    int j = 0 ;
    vector<int>b;
    while ( suma1 < suma && j < n ){
    suma1 += 2 * a[j] ;
    b.push_back(j);
    ++j;
    }
    o = abs(j-(n-j));
    ans=b;
    while ( next_permutation(v.begin(),v.end()) )
    {
    vector<int>r;
    suma1=0;
    j=0;
    while ( suma1 < suma && j < n ){
    suma1 += 2 * v[j].first;
    r.push_back(v[j].second);
    ++j;
    }
    int p = abs(j-(n-j));
    if ( p < o ){
    o=p;
    ans=r;
    }
    }
    vector<bool>fr(n+1,0);
    for ( auto it : ans ) fr[it]=1;
    for ( int i = 0 ; i < n ; ++ i )
    if ( !fr[i] ) ans.push_back(i);
    return ans;
}

