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

vector<int> v;
vector<int> 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];
            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;
    while (cnt<sz-1)
    {
        found=false;
        for (i=1; i<=n; i++)
        {
            if (!blocked[i] && sum+v[i]+smallsum(sz-1-cnt-1,i)<((s+1)/2))
            {
                nush.push_back(i);
                blocked[i]=1;
                cnt++;
                sum+=v[i];
                found=true;
                break;
            }
        }
        if (!found)
        {
            nush.clear();
            for (i=1; i<=n; i++)
                blocked[i]=0;
            return 0;
        }
    }
    ok=false;
    for (i=1; i<=n; i++)
    {
        if (!blocked[i] && sum+v[i]>=((s+1)/2))
        {
            blocked[i]=1;
            nush.push_back(i);
            for (auto x : nush)
            sol.push_back(x);
            ok=true;
            break;
        }
    }
    for (i=1;i<=n;i++)
    {
         if (!blocked[i])
             sol.push_back(i);
    }
    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);
    for (auto x : A)
        v2.push_back(x);
    sort(v2.begin(),v2.end());
    reverse(v2.begin(),v2.end());
    for (auto x : v2)
        v.push_back(x);
    n=A.size();
    s=0;
    int i,ts,sum;
    for (i=1; i<=n; i++)
        s+=v[i];
    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]];
         if (sum>=(s+1)/2)
             assert(0);
    }
    if (sum+v[sol[ts-1]]<(s+1)/2)
        assert(0);
    for (auto &x : sol)
         x--;
    return sol;
}


