//chockolateman

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

using namespace std;

const long long INF = 1e15;

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

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);
    preff[0] = 0;
    for(int i = 1 ; i <= N ; i++) //be carefull with 1 indexing here
        preff[i] = preff[i-1] + temp[i-1].first;
    ret.clear();
    for(int i = 0 ; i < N ; i++)
        ret.push_back(temp[i].second);
    for(int i = 0 ; i < N ; i++)
        used[i] = false;
    int med = (N-1)/2;
    used[temp[N-1].second] = true;
    ret[med] = temp[N-1].second;
    int pos = N-2;
    long long cur_val = 0; //val of element before last
    for(int i = med-1 ; i >= 0 ; i--)
    {
        while(cur_val + temp[pos].first + preff[i] >= (S+1)/2)
            pos--;
        cur_val += temp[pos].first;
        ret[i] = temp[pos].second;
        used[temp[pos].second]= true;
        pos--;
    }
    int l = 0;
    for(int i = med+1 ; i < N ; i++)
    {
        while(used[l])
            l++;
        ret[i] = l;
        l++;
    }
    return ret;
}