#include<iostream>
#include<vector>
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
#define pb push_back

vector<int> solve(vector<int> A) {
    ll n = A.size();
    vector<int> t(n);
    iota(t.begin(), t.end(), 0);
    sort(t.begin(), t.end(), [&](int x, int y) {
            return A[x] < A[y];
         });
    sort(A.begin(), A.end());
    ll S = 0;
    for (auto x : A)    S += x;
    ll l = 0, r = (n/2)*((n+1)/2), ans;
    while (l <= r) {
        ll m = (l+r)/2, s = 0;
        ll d = m;
        for (int i = (n+1)/2-1; i >= 0; --i) {
            if (d >= n/2)
                s += A[i+n/2], d-=n/2;
            else
                s += A[i+d], d = 0;
        }
        if (s >= (S+1)/2)
            r = m-1, ans = m;
        else
            l = m+1;
    }
    vector<int> p(n, 0), v;
    ll d = ans;
    for (int i = (n+1)/2-1; i >= 0; --i) {
        if (d >= n/2) {
            p[i+n/2]=1, v.pb(t[i+n/2]);
            d-=n/2;
        }
        else {
            p[i+d]=1, v.pb(t[i+d]);
            d = 0;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (!p[i])  v.pb(t[i]);
    }
    return v;
}