//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].second;
    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--;
        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++;
    }
    // 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;
    // }
    // for(int i = 0 ; i <= med ; i++)
    //     temp[i] = {A[ret[i]],ret[i]};
    // sort(temp,temp+med+1);
    // for(int i = 0 ; i <= med ; i++)
    //     ret[i] = temp[i].second;
    return ret;
}