#include "partition.h"
#include <algorithm>
#include <iostream>
std::vector<int> solve(std::vector<int> A) {
    int s=0;
    std::vector<std::pair<int,int>>v;
    int n=0;
    for(int i=0;i<A.size();i++){
        int e=A[i];
        v.push_back({e,n});
        n++;
        s+=e;
    }
    std::sort(v.begin(),v.end(),[](std::pair<int,int> a,std::pair<int,int> b){
        return a.first<b.first;
    });
    std::vector<int>ans;
    n--;
    int sum=0;
    for(int i=0;i<n/2;i++){
        ans.push_back(v[i].second);
        sum+=v[i].first;
    }
    ans.push_back(v[n].second);
    sum+=v[n].first;
    for(int i=n/2;i<n;i++){
        ans.push_back(v[i].second);
    }
    if(sum>=s/2) return ans;
    else{
        std::vector<int>ans1;
        for(int i=n/2+1;i<=n;i++){
            ans1.push_back(ans[i]);
        }
        for(int i=0;i<=n/2;i++){
            ans1.push_back(ans[i]);
        }
        return ans1;
    }
}
