#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;
}

Val v[2000000];

std::vector<int> solve(std::vector<int> A) {
    int n=(int)A.size(),i,l,r;
    for(i=0; i<n; i++){
        v[i].x=A[i];
        v[i].idx=i;
        if(i&&A[i]<A[i-1])
            std::swap(v[i], v[i-1]);
    }
    //std::sort(v, v+n);
    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&&i<n){
        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;
}
