#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> solve(std::vector<int> a){
    vector <pair <int,int> > b;
    int n = a.size();
    if(n % 2)exit(0);
    for(int i = 0;i < n;i++)b.push_back({a[i],i});
    sort(b.begin(),b.end());
    vector <int> p;
    int S = 0;
    for(int i = 0;i < n;i++)S += a[i];
    vector <int> pf(n);
    pf[0] = b[0].first;
    for(int i = 1;i < n;i++)
    {
        pf[i] = pf[i - 1] + b[i].first;
    }
    vector <int> used(n);
    for(int i = 0;i <= n / 2;i++)
    {
        int mn = 0;
        if(i)mn = pf[i - 1];
        if(2 * (pf[i + n / 2 - 1] - mn) >= S)
        {
            for(int j = i;j < i + n / 2;j++)
            {
                p.push_back(j);
                used[j] = 1;
            }
            break;
        }
    }
    for(int i = 0;i < n;i++)
    {
        if(used[i])continue;
        p.push_back(i);
    }
    for(int i = 0;i < n;i++)p[i] = b[p[i]].second;
    return p;
}