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

vector<int> solve(vector<int> A) {

    vector<pair<int, int>> s_ind;
    vector<int> res;
    int sum=0;
    for(int i=0;i<A.size();i++){
        s_ind.push_back({A[i], i});
        sum+=A[i];
    }
    sort(s_ind.begin(), s_ind.end());
    int new_sum=0;
    if(sum%2==0){
        sum=sum/2;
    }
    else{
        sum=sum/2+1;
    }
    int posl_ind;
    int i=0;
    while(new_sum<sum){
        posl_ind=A.size()-i;
        new_sum+=s_ind[i].first;
        res.push_back(s_ind[i].second);
        if(new_sum>=sum){
            i++;
            break;
        }
        new_sum+=s_ind[A.size()-i-1].first;
        res.push_back(s_ind[A.size()-i-1].second);
        i++;
    }

    while(i<posl_ind){
        res.push_back(s_ind[i].second);
        i++;
    }

    return res;
}
