//chockolateman

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

using namespace std;

const long long INF = 1e15;

int N;
long long preff[2000005];
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);
    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.assign(N-1,0);
    int med = (N-1)/2;
    ret[med] = temp[N-1].second;
    int pos = N-2;
    long long cur_val = 0; //val of element before last
    int r = med+1;
    for(int i = med-1 ; i >= 0 ; i--)
    {
        while(cur_val + temp[pos].first + preff[i] >= (S+1)/2)
        {
            ret[r] = temp[pos].second;
            r++;
            pos--;
        }
        cur_val += temp[pos].first;
        ret[i] = temp[pos].second;
        pos--;
    }
    while(r < N)
    {
        ret[r] = temp[pos].second;
        pos--;
        r++;
    }
    return ret;
}