#include <bits/stdc++.h>
#include "partition.h"
using namespace std;

#define pb push_back
using ll = long long;
// #define int ll
using pi = array<int, 2>;
using ti = array<int, 3>;

deque<pi> RR;

vector<int> solve(vector<int> A) {
  int n = A.size();
  
  ll total = 0;
  vector<pi> a(n);
  for (int i = 0; i < n; ++i) {
    a[i] = {A[i], i};
    total += a[i][0];
  }
  // sort(a.begin(), a.end());
  
  ll sum = 0;
  for (int i = 0; i < (n + 1) / 2; ++i) {
    sum += a[i][0];
  }
  
  RR.clear();
  for (int i = (n + 1) / 2; i < n; ++i) {
    RR.pb({a[i][0], i});
  }
  
  int ptr = (n + 1) / 2 - 1;
  while (ptr >= 0 && sum < (total + 1) / 2) {
    auto big = RR.back();
    RR.pop_back();
    sum = sum - a[ptr][0] + big[0];
    swap(a[ptr], a[big[1]]);
    RR.push_front({a[big[1]][0], big[1]});
    
    --ptr;
  }
  assert(sum >= (total + 1) / 2);
  
  vector<int> ans(n);
  for (int i = 0; i < n; ++i) {
    ans[i] = a[i][1];
  }
  return ans;
}
