#include "partition.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 3e6 + 10;
//vector < pair < int, int > > g;
int n,  used[maxn];
std::vector<int> solve(std::vector<int> A)
{

    n = A.size();
    long long total = 0;
    for (int i = 0; i < n; ++ i)
        total += A[i];
    for (int i = 0; i < n; ++ i)
        used[i] = 0;
    int mindif = n;
    vector < int > ans;
    for (int mask = 0; mask < (1 << n); ++ mask)
    {
        vector < pair < int, int > > onf, ons;
        for (int i = 0; i < n; ++ i)
        {
            if((1 << i) & mask)onf.pb(make_pair(A[i], i));
            else ons.pb(make_pair(A[i], i));
        }
        sort(onf.begin(), onf.end());
        sort(ons.begin(), ons.end());
        vector < int > curr;
        for (auto &[x, pos]: onf)curr.pb(pos);
        for (auto &[x, pos]: ons)curr.pb(pos);

        long long sum = 0, last = -1, p = 0;
        while(sum * 2 < total)
        {
            sum += A[curr[p]];
            p ++;
            last = p;
        }
        p ++;
        int ost = n -  p;
        int diff = abs(p - ost);
        if(diff < mindif)
        {
            swap(ans, curr);
            mindif = diff;
        }
    }
    /*//g.clear();
    vector < int > ans;
    long long total = 0;
    for (int i = n; i >= 1; -- i)
    {
        if(used[i])continue;
        total += i;
        used[i] = 1;
        used[n+1 -i]  =1;
        ans.pb(i-1);
        if(i != (n+1-i))ans.pb(n+1-i-1);
    }
    long long sum = 0;
    for (int i = 0; i < (n)/2 + 1; ++ i)
        sum += 1LL * ans[i] + 1;
    if(sum < total/2 && n > 3)
        swap(ans[n-1], ans[n/2-1]);*/
    return ans;
}
