#include<bits/stdc++.h>
#include "partition.h"
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct cell
{
    int ind,st;
};
bool cmp(cell a1,cell a2)
{
    return a1.st<a2.st;
}
int t,n;
long long int p[2000005];
cell a[2000005];
vector<int> solve(vector<int> A)
{
    vector<int>otg;
    n=A.size();
    long long int sum=0;
    for(int i=1; i<=n; i++)
    {
        a[i].st=A[i-1];
        a[i].ind=i;
        sum+=a[i].st;
    }
    sort(a+1,a+n+1,cmp);
    p[n+1]=0;
    for(int i=n;i>=1;i--)
    {
        p[i]=p[i+1]+a[i].st;
    }
    long long int st=0,br=(n+1)/2,to=1;
    while(br)
    {
        if(st+p[n-br+1]+a[to].st<sum/2)break;
        otg.push_back(a[to].ind-1);
        st+=a[to].st;
        br--;
        to++;
    }
    int cur=n;
    while(br)
    {
        otg.push_back(a[cur].ind-1);
        cur--;
        br--;
    }
    for(int i=to;i<=cur;i++)
    {
        otg.push_back(a[i].ind-1);
    }
    return otg;
}
