#include "partition.h"
#include <vector>
#include <utility>
#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<cmath>
#include<random>
using namespace std;
using ll = long long;
#define V vector
#define VI V<int>
#define rep(i,a,b,step) for(int i=int(a);i<=int(b);i+=int(step))
#define repl(i,a,b,step) for(int i=int(a);i>=int(b);i-=int(step))
#define ff first
#define ss second
#define pq priority_queue
mt19937 rd(time(nullptr));
std::vector<int> solve(std::vector<int> a) {
    int n = a.size(), l = 0, r = 0, mn = n;
    ll sum1 = 0, sum2;
    VI ans(n), p(n);
    V<bool>used(n);
    rep(i, 0, n - 1, 1)sum1 += a[i], p[i] = i;
    auto cmp = [&](int i, int j) {
        return a[i] < a[j];
    };
    sort(begin(p), end(p), cmp);
    rep(i, 0, n - 1, 1) {
        sum2 = 0;
        rep(j, i, n - 1, 1) {
            sum2 += a[p[j]];
            if (sum2 * 2 >= sum1 - sum2) {
                if (mn > abs(n - 2 * (j - i + 1))) {
                    mn = abs(n - 2 * (j - i + 1));
                    l = i;
                    r = j;
                }
                break;
            }
        }
    }
    rep(i, 0, r - l, 1)ans[i] = p[l + i], used[l + i] = 1;
    int x = 0;
    rep(i, r - l + 1, n - 1, 1) {
        while (x < n and used[x])x++;
        used[x] = 1;
        ans[i] = x;
    }
    return ans;
}