#include "partition.h"
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include <random>
#include <chrono>
#include <set>
#include <unordered_map>
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using namespace std;

#define V vector
#define rep(a, b, c, d) for (int a = b; a <= c; a += d)
#define repl(a, b, c, d) for (int a = b; a >= c; a -= d)
#define pb push_back
#define ll long long 
#define all(v) v.begin(), v.end()
#define sz(x) int(x.size())
#define pli pair<ll, int>
#define ff first
#define ss second

vector<int> solve(std::vector<int> a) {
	V<pli> tv;
	int n = sz(a);
	rep(i, 0, n - 1, 1) {
		tv.pb({ a[i], i });
	}
	sort(all(tv));

	V<int> ans(n);

	rep(i, 0, n - 2, 2) {
		ans[(i >> 1)] = tv[i].ss;
	}
	rep(i, 1, n - 1, 2) {
		ans[(i >> 1) ^ 1 + (n >> 1)] = tv[i].ss;
	}
	return ans;
	V<ll> suf(n + 1, 0);
	V<ll> pref(n, 0);
	pref[0] = tv[0].ff;
	rep(i, 1, n - 1, 1) {
		pref[i] = pref[i - 1] + tv[i].ss;
	}
	int goal = (n + 1) >> 1;
	
}
