#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();
	vector<int>p(n), ans(n);
    ll sum1, sum2 = 0;
    for (int i = 0; i < n; ++i)p[i] = i, sum2 += a[i];
	int mn = n;
	for (int i = 0; i < 1000; ++i) {
		shuffle(begin(p), end(p), rd);
        sum1 = 0;
        for (int j = 0; j < n; ++j) {
            sum1 += a[p[j]];
            if (sum1 * 2 >= sum2) {
                if (mn > abs(j + 1 - (n - j - 1))) {
                    mn = abs(j + 1 - (n - j - 1));
                    ans = p;
                }
                break;
            }
        }

	}
	return ans;
}