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

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();
    if(n>100){
        int i,l,r,pivot;
        long long sum=0,cur=0;

        for(i=0; i<n; i++){
            sum+=A[i];
        }
        pivot=sum/n;
        sum=sum/2+sum%2;

        l=0;r=n-1;
        for(i=0; i<n; i++){
            if(A[i]<pivot){
                v[l].x=A[i];
                v[l].idx=i;
                l++;
            }else{
                v[r].x=A[i];
                v[r].idx=i;
                r--;
            }
        }
        for(i=n/2; i<n-1; i++){
            if(v[i].x>v[i+1].x)
                std::swap(v[i], v[i+1]);
            cur+=v[i].x;
        }

        i=n/2;
        std::vector <int> ans;
        while((cur>=sum||cur+v[n-1].x<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;
    }else{
        int i,l,r;
        for(i=0; i<n; i++){
            v[i].x=A[i];
            v[i].idx=i;
        }
        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){
            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;
    }
    return {};
}
