#include "partition.h"
#include <algorithm>
#include <vector>
#include <utility>
#include <map>

using namespace std;

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

    int N = (int)A.size();

    vector<pair<int,int>> V;
    vector<int> res;
    vector<int> B;
    vector<pair<int,int>> rem;

    for(int i=0;i<N;++i) {    
        V.push_back({A[i],i});
    }
    sort(V.begin(),V.end());

    for(int i=0;i<N;++i) {
        if (i != N-1 and V[i].first == V[i+1].first) {
            B.push_back(V[i].second);
            res.push_back(V[i+1].second);
            i++;
        }
        else rem.push_back(V[i]);
    }
    
    long long int a = 0;
    long long int b = 0;
    vector<int> C;
    vector<int> D;

    int M = (int)rem.size();

    bool l = 0;
    for(int i=0;i<M;++i) {
        if (a <= b) {
            D.push_back(rem[i].second);
            a += rem[i].first;
            l = 0;
        }
        else {
            C.push_back(rem[i].second);
            b += rem[i].first;
            l = 1;
        }
    }
    if (l) {
        for(int i=0;i<(int)C.size();++i) res.push_back(C[i]);
        for(int i=0;i<(int)B.size();++i) res.push_back(B[i]);
        for(int i=0;i<(int)D.size();++i) res.push_back(D[i]);
    }
    else {
        for(int i=0;i<(int)D.size();++i) res.push_back(D[i]);
        for(int i=0;i<(int)B.size();++i) res.push_back(B[i]);
        for(int i=0;i<(int)C.size();++i) res.push_back(C[i]);
    }

    return res;
}
