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

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

    vector<pair<int, int>> s_ind;
    vector<int> res1;
    vector<int> res2;
    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 sbor1=0, sbor2=0;
    int a=1;
    for(int i=0;i+1<A.size();i++){
        if(s_ind[i].first>=s_ind[i+1].first){
            if(a%2==0){
                res1.push_back(s_ind[i].second);
                res2.push_back(s_ind[i+1].second);
                sbor1+=s_ind[i].first;
                sbor2+=s_ind[i+1].first;
            }
            else{
                res2.push_back(s_ind[i].second);
                res1.push_back(s_ind[i+1].second);
                sbor2+=s_ind[i].first;
                sbor1+=s_ind[i+1].first;
            }
        }
        else{
            if(a%2==0){
                res2.push_back(s_ind[i].second);
                res1.push_back(s_ind[i+1].second);
                sbor2+=s_ind[i].first;
                sbor1+=s_ind[i+1].first;
            }
            else{
                res1.push_back(s_ind[i].second);
                res2.push_back(s_ind[i+1].second);
                sbor1+=s_ind[i].first;
                sbor2+=s_ind[i+1].first;
            }
        }
        a++;
    }
    if(A.size()%2!=0){
        if(sbor1<sbor2){
            sbor1+=s_ind[A.size()-1].first;
            res1.push_back(s_ind[A.size()-1].second);
        }
        else{
            sbor2+=s_ind[A.size()-1].first;
            res2.push_back(s_ind[A.size()-1].second);
        }
    }
    for(int i=0;i<=A.size()/2;i++){
        res1.push_back(res2[i]);
    }
    return res1;
}
