#include "partition.h"
#define int long long
#include<iostream>
#include<vector>
using namespace std;
#include<algorithm>
int s[2000005];
pair<int,int> v[2000005];
vector<int> solve(vector<int> A) {
    //vector<int> test;
    //test.push_back(1);
   // return test;

    int sum=0;
    for(int i=0;i<=A.size()-1;i++)
    {
        v[i].first=2*A[i];
        sum+=v[i].first;
        v[i].second=i;
    }
    sum/=2;
    int n=A.size();
    sort(v,v+n);
    int k;
    if(n%2)
        k=n/2+1;
    else
        k=n/2;
    for(int i=0;i<n;i++)
    {
        if(i)
            s[i]=s[i-1]+v[i].first;
        else
            s[i]=v[i].first;
    }
    int ii=0;
    int j=n-k;
    int ok=1;
    int st=0;
    int dr=s[n-1]-s[n-k-1];
    while(ok || ii>k)
    {
        if(st+dr-v[n-1].first<sum)
        {
            ok=0;
        }
        else
        {
            st+=v[ii].first;
            ii++;
            dr-=v[j].first;
            j++;
        }
    }
    vector<int> rasp;
    for(int i=0;i<ii;i++)
    {
        rasp.push_back(v[i].second);
    }
    for(int i=j;i<n;i++)
    {
        rasp.push_back(v[i].second);
    }
    for(int i=ii;i<j;i++)
    {
        rasp.push_back(v[i].second);
    }
    return rasp;
}