//chockolateman

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

using namespace std;

const long long INF = 1e15;

int N;
pair<int,int> temp[2000005];
vector<int> ret;

std::vector<int> solve(std::vector<int> A) {
    N = A.size();
    long long S = 0;
    for(int i = 0 ; i < N ; i++)
    {
        temp[i] = {A[i],i};
        S += A[i];
    }
    sort(temp,temp+N);
    ret.clear();
    for(int i = 0 ; i < N ; i++)
        ret.push_back(temp[i].second);
    int med = (N-1)/2;
    long long cur_sum = 0;
    for(int i = 0 ; i <= med ; i++)
        cur_sum += A[ret[i]];
    while(cur_sum < (S+1)/2)
    {
        int posx = 0;
        int posy = 0;
        long long cur_diff = INF;
        for(int i = 0 ; i <= med ; i++)
            for(int j = med + 1 ; j < N ; j++)
                if(A[ret[i]] < A[ret[j]] && cur_diff > A[ret[j]] - A[ret[i]])
                {
                    cur_diff = A[ret[j]] - A[ret[i]];
                    posx = i;
                    posy = j;
                }
        swap(ret[posx],ret[posy]);
        cur_sum += cur_diff;
    }
    return ret;
}