#include "partition.h"
struct pair{
    int first;
    int second;
};
std::vector<int> solve(std::vector<int> A) {
    
    std::vector<pair> AA;
    for(int i=0; i<A.size(); i++){
        AA.push_back({A[i], i});
    }
    sort(AA.begin(), AA.end());
    reverse(AA.begin(), AA.end());
    int sum1=A[0], sum2=0;
    std::vector<int> red1;
    std::vector<int> red2;
    red1.push_back(AA[0].second);

    for(int i=1; i<AA.size(); i++){
        if(sum1>sum2){
            sum2+=AA[i].first;
            red2.push_back(AA[i].second);
        }
        else{
            sum1+=AA[i].first;
            red1.push_back(AA[i].second);
        }
    }
    if(sum1<sum2){
        for(int i=0; i<red1.size();i++){
            red2.push_back(red1[i]);
        }
        return red2;
    }
    else{
        for(int i=0; i<red2.size();i++){
            red1.push_back(red2[i]);
        }
        return red1;
    }
}
