#include "partition.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#define R0F(i,a) ROF(i,0,a)
#define sz(v) v.size()
#define mp make_pair
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vpi vector<pi>
#define vpl vector<pl>
#define vb vector<bool>
#define f first
#define s second
#define pb push_back

ll sum, n;

vi check(vpl &v, int k){
    ll cur = 0;
    F0R(i, k)cur += v[i].f;
    if(cur > sum)return {-1};
    int ind = n - 1;
    if(sum <= cur + v[ind].f){
        vi rez;
        F0R(i, k)rez.pb(v[i].s);
        rez.pb(v[ind].s);
        FOR(j, k, n){
            if(j == ind)continue;
            rez.pb(v[j].s);
        }
        return rez;
    }
    FOR(i, k, n){
        cur += v[i].f;
        cur -= v[i - k].f;
        if(cur >= sum)return {-1};
        //cerr << sum << " " << cur << endl;
        int ind1 = n - 1;
        int ind2 = i - k;
        if(i != ind1 && cur + v[ind1].f >= sum){
            vi rez;
            FOR(j, i - k + 1, i + 1)rez.pb(v[j].s);
            rez.pb(v[ind1].s);
            F0R(j, i - k + 1){
                if(j == ind1)continue;
                rez.pb(v[j].s);
            }
            FOR(j, i + 1, n){
                if(j == ind1)continue;
                rez.pb(v[j].s);
            }
            return rez;
        }
        if(cur + v[ind2].f >= sum){
            vi rez;
            FOR(j, i - k + 1, i + 1)rez.pb(v[j].s);
            rez.pb(v[ind2].s);
            F0R(j, i - k + 1){
                if(j == ind2)continue;
                rez.pb(v[j].s);
            }
            FOR(j, i + 1, n){
                if(j == ind2)continue;
                rez.pb(v[j].s);
            }
            return rez;
        }
    }
    return {-1};
}

vi solve(vi a) {
    vi reshi;
    n = sz(a);
    if(n == 1){
        return {0};
    }
    vpl v(n);
    F0R(i, n)v[i] = {a[i], i};
    sort(v.begin(), v.end());
    sum = 0;
    F0R(i, n)sum += a[i];
    sum = sum / 2 + (sum % 2);
    ll nes = 0;
    ll l = 0, r = n / 2, sol = -1;
    vi st;
    while(nes < sum){
        nes += v[n - l - 1].f;
        l++;
    }
    //cerr << l << " " << r << endl;
    while(l <= r){
        ll md = (l + r) / 2;
        vi x = check(v, md - 1);
        if(x[0] != -1){
            sol = md;
            st = x;
            l = md + 1;
        }
        else r = md - 1;
    }
    //cerr << sol << endl;
    //cerr << sol << " " << st << endl;
    return st;
}
