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

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