#include <bits/stdc++.h>

using namespace std;
#define ll long long

std::vector<int> solve(std::vector<int> A) {
  ll n = A.size();
  unordered_map<ll, queue<ll>> val_to_idx;
  for (ll i = 0; i < n; ++i) {
    val_to_idx[A[i]].push(i);
  }

  sort(A.begin(), A.end());
  vector<ll> sss(n, 0);
  sss[0] = A.front();
  for (ll i = 1; i < n; ++i) {
    sss[i] = sss[i-1]+A[i];
  }

  ll m = sss.back()/2+sss.back()%2;
  ll last = 0;
  ll front = 0;
  for (ll i = n-1; i > 0; --i) {
    ++last;
    if (sss.back()-sss[i-1] >= m) {
      break;
    }
  }

  ll res = sss.back()-sss[n-1-last];
  ll old_used = 1e15;
  ll oldest_l;
  ll oldest_r;
  for (ll i = 0; i < n; ++i) {
    if (last+front >= n/2) {
      oldest_l = last;
      oldest_r = front;
      break;
    }
    ll old_front = front;
    ll old_last = last;
    ++front;
    res += A[front-1];
    while (res >= m+A.back()) {
      res -= A[n-last];
      --last;
      if (last < 0) {
        break;
      }
      for (ll j = i+1; j < n; ++j) {
        if (res >= m) {
          break;
        }
        ++front;
        res += A[front-1];
      }
    }
    if (last < 0) {
      last = old_last;
      front = old_front;
      break;
    }
    if (abs((last+front)-n/2)>abs(old_used-n/2)) {
      break;
    }
    oldest_l = last;
    oldest_r = front;
  }
  vector<int> perm;
  for (ll i = 0; i < oldest_r; ++i) {
    perm.push_back(val_to_idx[A[i]].front());
    val_to_idx[A[i]].pop();
  }
  for (ll i = n-oldest_l; i < n; ++i) {
    perm.push_back(val_to_idx[A[i]].front());
    val_to_idx[A[i]].pop();
  }
  for (ll i = oldest_r; i < n-oldest_l; ++i) {
    perm.push_back(val_to_idx[A[i]].front());
    val_to_idx[A[i]].pop();
  }
  return perm;
}

//signed main() {
//  ll tests;
//  cin >> tests;
//  for (ll t = 0; t < tests; ++t) {
//    ll a;
//    cin >> a;
//    vector<ll> val(a);
//    for (ll i = 0; i < a; ++i) {
//      cin >> val[i];
//    }
//    val = solve(val);
//    for (ll i : val) {
//      cout << i << " ";
//    }
//    cout << endl;
//  }
//}