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

int check(vpl &v, int k){
    ll cur = 0;
    F0R(i, k)cur += v[i].f;
    if(cur > sum && cur - v[k - 1].f > sum)return -1;
    if(cur > sum)return 0;
    FOR(i, k, n){
        cur += v[i].f;
        cur -= v[i - k].f;
        if(cur >= sum)return i - k + 1;
    }
    return -1;
}

vi solve(vi a) {
    n = sz(a);
    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);
    vi reshi;
    if(v[n - 1].f >= sum){
        F0R(i, (n - 1) / 2)reshi.pb(v[i].s);
        reshi.pb(v[n - 1].s);
        FOR(i, (n - 1) / 2, n - 1)reshi.pb(v[i].s);
        return reshi;
    }
    ll nes = 0;
    ll l = 0, r = n / 2, sol = -1, st = -1;
    while(nes < sum){
        nes += v[n - l - 1].f;
        l++;
    }
    //cerr << l << " " << r << endl;
    while(l <= r){
        ll md = (l + r) / 2;
        ll x = check(v, md);
        if(x != -1){
            sol = md;
            st = x;
            l = md + 1;
        }
        else r = md - 1;
    }
    //cerr << sol << " " << st << endl;
    FOR(i, st, st + sol)reshi.pb(v[i].s);
    F0R(i, st)reshi.pb(v[i].s);
    FOR(i, st + sol, n)reshi.pb(v[i].s);
    return reshi;
}
