#include<bits/stdc++.h>
#include "partition.h"
using namespace std;
const long long maxn=1e6;
vector<int>a;
vector<int>v;
bool cmp(int ah,int b)
{
    return a[ah]<a[b];
}
std::vector<int> solve(std::vector<int> A)
{
    int n=A.size();
    int s=0;
    a.clear();
    v.clear();
    for(int i=0;i<n;i++)
    {
        a.push_back(A[i]);
        v.push_back(i);
        s+=a.back();
    }
    sort(v.begin(),v.end(),cmp);
    if(s%2)s++;
    s/=2;
    int l=n-1;
    if(n%2)n++;
    int h=0;
    for(int i=0;i<n/2;i++)
    {
        h+=a[v[i]];
        if(h>=s)return v;
    }
    for(int i=n/2-1;i>=0;i--)
    {
        h-=a[v[i]];
        swap(a[l],a[v[i]]);
        h+=a[v[i]];
        if(h>=s)return v;
    }
    return v;
}
