#include <bits/stdc++.h>
#include "partition.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

struct nsuh
{
    int val;
    int pos;
};

bool cmp(nsuh a, nsuh b)
{
    return a.val<b.val;
}

vector<nsuh> v;
vector<nsuh> v2;
vector<signed> sol;
int n;
int s;
bool blocked[1000005];

int smallsum(int cnt, int idx)
{
    int sum,i;
    sum=0;
    for (i=n; i>=1; i--)
    {
        if (i==idx)
            continue;
        if (!blocked[i] && cnt!=0)
        {
            sum+=v[i].val;
            cnt--;
        }
    }
    return sum;
}

bool check(int sz)
{
    if (sz==0)
        return 0;
    int sum,cnt,i;
    bool ok,found;
    vector<int> nush;
    sum=0;
    cnt=0;
    i=1;
    while (cnt<sz-1)
    {
        if (!blocked[i] && sum+v[i].val+smallsum(sz-1-cnt-1,i)<((s+1)/2))
        {
            nush.push_back(v[i].pos);
            blocked[i]=1;
            cnt++;
            sum+=v[i].val;
        }
        i++;
        if (i>n && cnt!=(sz-1))
        {
            nush.clear();
            for (i=1; i<=n; i++)
                blocked[i]=0;
            return 0;
        }
    }
    ok=false;
    sol.clear();
    for (i=1; i<=n; i++)
    {
        if (!blocked[i] && sum+v[i].val>=((s+1)/2))
        {
            blocked[i]=1;
            nush.push_back(v[i].pos);
            for (auto x : nush)
                sol.push_back(x);
            ok=true;
            break;
        }
    }
    for (i=1; i<=n; i++)
    {
        if (!blocked[i])
            sol.push_back(v[i].pos);
    }
    nush.clear();
    for (i=1; i<=n; i++)
        blocked[i]=0;
    return ok;
}

std::vector<signed> solve(std::vector<signed> A)
{
    v.push_back({0,0});
    int i;
    for (i=0; i<A.size(); i++)
        v2.push_back({A[i],i+1});
    sort(v2.begin(),v2.end(),cmp);
    reverse(v2.begin(),v2.end());
    for (auto x : v2)
        v.push_back(x);
    n=A.size();
    s=0;
    int ts,sum;
    for (i=1; i<=n; i++)
        s+=v[i].val;
    sol.clear();
    for (i=(n+1)/2; i<=n; i++)
    {
        if (check(i)==1)
        {
            ts=i;
            break;
        }
        else if (check(n-i)==1)
        {
            ts=n-i;
            break;
        }
    }
    v.clear();
    v2.clear();
    sum=0;
    for (i=0; i<ts-1; i++)
    {
        sum+=v[sol[i]].val;
    }
    for (auto &x : sol)
        x--;
    return sol;
}


