#include <bits/stdc++.h>
#include "partition.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2")

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

const int N = 2e6 + 5;
pi a[N];

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

/*
1 1 3 3 4 4 5 6 6
*/
