    #include "partition.h"
    #include <bits/stdc++.h>
    #define ll long long
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define fi first
    #define sc second
    #define pb push_back
    #define all(x) (x).begin(),(x).end()

    using namespace std;

    const int MAXN = 2e5;
    const ll inf = 1e18;
    const int MAXV = (3e7) + 5;

    std::vector<int> solve(std::vector<int> A) {
        ll sum = 0;
        int n = (int)A.size();
        vector<int> rez;
        for(int i=0; i<n; i++)sum+=A[i];
        ll goal = (sum+1)/2;
        vector<pii> niz(n);
        for(int i=0; i<n; i++)niz[i].fi = A[i], niz[i].sc = i;
        sort(all(niz));
        int index1 = 0;
        int index2 = n-1;
        int indexpola = (n-1)/2;
        ll sumapola = 0;
        for(int i=0; i<(n+1)/2; i++)sumapola+= niz[i].fi;
        //for(auto x: niz)cout << x.fi << " ";cout << endl;
        while(sumapola < goal)
        {
            if(sumapola-niz[indexpola].fi + niz[index2].fi >= goal)
            {
                swap(niz[indexpola], niz[index2]);
                break;
            }
            else
            {
                 sumapola-=niz[index1].fi;
                 sumapola+=niz[index2].fi;
                 swap(niz[index1], niz[index2]);
                 index1++;
                 index2--;
            }
            //for(auto x: niz)cout << x.fi << " ";cout << endl;
        }
        for(auto x: niz)rez.pb(x.sc);
        //for(auto x: niz)cout << x.fi << " ";cout << endl;
        return rez;
    }
