#include "partition.h"
#include<bits/stdc++.h>
using namespace std;

std::vector<int> solve(std::vector<int> A) {
    int n=A.size();
    vector<pair<int,int>> niz(n);
    for(int i=0; i<n; i++)
        niz[i]={A[i],i};
    sort(niz.begin(),niz.end());

    long long prvih[n];
    prvih[0]=niz[0].first;
    for(int i=1; i<n; i++)
        prvih[i]=niz[i].first+prvih[i-1];
    long long S=prvih[n-1];
    int a=n/2,b=n-a;
    vector<int> rez(n);
    long long poslednjih=0;
    for(int i=0; 1; i++){
        if(prvih[a-1-i]+poslednjih>=(S+1)/2){
            int indx=-1;
            for(int j=0; j<=a-1-i; j++) rez[++indx]=niz[j].second;
            for(int j=0; j<i; j++) rez[++indx]=niz[n-1-j].second;
            for(int j=a-i; j<=n-i-1; j++) rez[++indx]=niz[j].second;
            break;
        }
        poslednjih+=niz[n-1-i].first;
    }

    return rez;
}
