#include <iterator>
#include <set>
#include <vector>
#include "algorithm"
typedef long long ll;
struct sister {
  std::set<std::pair<ll, int>> values;
  ll s;
  std::pair<ll, int> top() {
    return *std::prev(values.end());
  }
  std::pair<ll, int> bot() {
    return *values.begin();
  }
  void add(ll v, int i) {
    s += v;
    values.insert({v, i});
  }
  void del(ll v, int i) {
    s -= v;
    values.erase({v, i});
  }
  ll sum() {
    return s;
  }
};
std::vector<int> solve(std::vector<int> A) {
  if(A.size() == 1) return {0};
  std::vector<std::pair<int, int>> srt;
  for(int i = 0; i < A.size(); ++i) srt.push_back({A[i], i});
  ll sum = 0;
  for(int i : A) sum += i;
  sum = (sum+1)/2;
  std::sort(srt.begin(), srt.end());
  sister a, b;
  for(int i = 0; i < A.size()/2; ++i) a.add(srt[i].first, srt[i].second);
  for(int i = A.size()/2; i < A.size(); ++i) b.add(srt[i].first, i);
  while(a.sum() < sum) {
    auto t1 = b.top();
    auto t2 = a.bot();
    a.del(t2.first, t2.second);
    b.del(t1.first, t1.second);
    a.add(t1.first, t1.second);
    b.add(t2.first, t2.second);
  }
  std::vector<int> sol;
  for(auto ai : a.values) sol.push_back(ai.second);
  for(auto ai : b.values) sol.push_back(ai.second);
  return sol;
}
