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

struct Val{
    int x,idx;
};

bool operator < ( const Val & a, const Val & b ){
    return a.x<b.x;
}

std::vector <Val> v;

std::vector<int> solve(std::vector<int> A) {
    int n=(int)A.size(),i,l,r;
    v.clear();
    for(i=0; i<n; i++)
        v.push_back({A[i], i});
    std::sort(v.begin(), v.end());
    long long sum,cur;
    sum=cur=0;
    for(i=0; i<n; i++){
        sum+=v[i].x;
        if(i>=n/2&&i<n-1)
            cur+=v[i].x;
    }
    sum=sum/2+sum%2;
    i=n/2;
    std::vector <int> ans;
    while(cur>=sum){
        cur=cur-v[i].x+v[i-n/2].x;
        ans.push_back(v[i-n/2].idx);
        i++;
    }
    l=i-n/2;
    r=i;
    for(; i<n; i++)
        ans.push_back(v[i].idx);
    for(i=l; i<r; i++)
        ans.push_back(v[i].idx);
    return ans;
}
