#include "partition.h"

#include <iostream>
#include <vector>
#include <algorithm>


#define X first
#define Y second
#define control std::cout<<"passed\n";
#define maxn 200005
#define maxlog 21
#define PB push_back

#pragma GCC optimize("Ofast" , "O3" , "unroll-loops")
#pragma GCC target("avx2")


typedef long long ll;
typedef std::pair <ll, ll> pll;


std::vector<int> solve(std::vector<int> a)
{
    ll sum = 0;

    ll n = a.size();
    std::vector <ll> p(n, 0);
    for(ll i = 0; i < n; i++)
        p[i] = i;

    for(ll i = 0; i <n; i++)
        sum += a[i];

    std::sort(p.begin(), p.end(), [&](ll i, ll j)
    {
        return a[i] < a[j];
    });

    std::sort(a.begin(), a.end());


    std::vector <ll> pref(n + 2, 0), suff(n + 2, 0);
    for(ll i = 0; i < n; i++)
        pref[i + 1] = pref[i] + a[i];
    for(ll i = n - 1; i >= 0; i--)
        suff[i + 1] = suff[i + 2] + a[i];

    ll ans = 1e9;
    ll lel = 0, rir = 0;

    for(ll le = 0; le < n; le++)
    {
        for(ll ri = 0; ri + le < n; ri++)
        {
            ll sum1 = pref[le] + suff[n - ri + 1];

            //std::cout << le << " " << ri << " " << sum1 << "\n";

            if(sum1 < sum / 2)
                continue;
            if(sum1 - a[n - 1] > sum / 2)
                continue;

            //std::cout << "valid" << "\n";

            ll br1 = le + ri;
            ll br2 = n - (le + ri);
            //std::cout << "!! " << abs(br1 - br2) << "\n";

            if(ans > abs(br1 - br2))
            {
                ans = abs(br1 - br2);
                lel = le;
                rir = ri;
            }
        }
    }

    //std::cout << ans << " " << lel << " " << rir <<"\n";

    std::vector <bool> used(n, false);
    std::vector <int> ret;
    ll pp = 0;
    while(lel--)
    {
        ret.PB(p[pp]);
        used[p[pp]] = true;
        pp++;
    }

    bool lamp = false;
    if(rir > 0)
        lamp = true , rir--;
    pp = n - 2;
    while(rir--)
    {
        ret.PB(p[pp]);
        used[p[pp]] = true;
        pp--;
    }
    if(lamp == true)
        ret.PB(p[n - 1]), used[p[n - 1]] = true;



    /**for(auto& e : a)
        std::cout << e << " ";
    std::cout << "\n";
    for(auto& e : p)
        std::cout << e << " ";
    std::cout << "\n";*/

    for(ll i = 0; i < n; i++)
        if(used[i] == false)
            ret.PB(i);
    return ret;
}
