#include "partition.h"
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long llong;

const int MAXN = 2e6 + 10;

int n;
int a[MAXN];
llong sum;

bool check(vector < pair < int, int > >& v)
{
    llong cur = 0;

    for(int i = 0; i < v.size() - 1; i++)
    {
        cur += v[i].first;

        if(2LL * cur >= sum)
            return false;
    }

    cur += v.back().first;

    return 2LL * cur >= sum;
}

int getdiff(vector < int >& p)
{
    llong cur = 0;

    for(int i = 0; i < p.size(); i++)
    {
        cur += a[p[i]];

        if(2LL * cur >= sum)
            return abs((i + 1) - (n - i - 1));
    }

    return -1;
}

std::vector < int > solve(std::vector < int > A) 
{
    n = A.size();

    sum = 0;

    for(int i = 0; i < n; i++)
    {
        sum += A[i];
        a[i] = A[i];
    }

    int mindiff = n;
    vector < int > ans(n);

    for(int mask = 0; mask < (1 << n); mask++)
    {
        vector < pair < int, int > > s1;
        vector < pair < int, int > > s2;

        for(int i = 0; i < n; i++)
        {
            if(mask & (1 << i))
            {
                s1.push_back({A[i], i});
            }
            else
            {
                s2.push_back({A[i], i});
            }
        }

        int sz1 = s1.size();
        int sz2 = s2.size();

        int diff = abs(sz1 - sz2);

        if(diff >= mindiff)
            continue;

        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());

        if(check(s1))
        {
            vector < int > p;

            for(int i = 0; i < sz1; i++)
            {
                p.push_back(s1[i].second);
            }

            for(int i = 0; i < sz2; i++)
            {
                p.push_back(s2[i].second);
            }

            if(mindiff > diff)
            {
                mindiff = diff;
                ans = p;
            }
        }
        else if(check(s2))
        {
            vector < int > p;

            for(int i = 0; i < sz2; i++)
            {
                p.push_back(s2[i].second);
            }

            for(int i = 0; i < sz1; i++)
            {
                p.push_back(s1[i].second);
            }

            if(mindiff > diff)
            {
                mindiff = diff;
                ans = p;
            }
        }
    }

    //cout << "Diff : " << getdiff(ans) << endl;

    return ans;
}
