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

std::vector<int> solve(std::vector<int> A) {
  int n = (int)A.size();
  vector<pair<long long, long long>> a;
  for (int i = 0; i < n; ++i) {
    a.push_back({A[i], i});
  }
  sort(a.begin(), a.end());
  vector<long long> pref(n);
  pref[0] = a[0].first;
  for (int i = 1; i < n; ++i) {
    pref[i] = pref[i - 1] + a[i].first;
  }
  long long sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += a[i].first;
  }
  long long mn = n;
  for (int can = 1; can <= n; ++can) {
    long long cur = 0;
    for (int i = 0; i < can; ++i) {
      cur += a[i].first;
    }
    long long lo = 1, hi = can, best = 0;
    while (lo <= hi) {
      long long mid = (lo + hi) >> 1;
      int l = mid - 1, r = n - mid;
      if (l >= r) {
        hi = mid - 1;
        continue;
      }
      long long u = pref[l];
      long long v = pref[n - 1] - (!r ? 0 : pref[r - 1]);
      long long k = cur - u + v;
      if (k >= (sum + 1) / 2) {
        best = k;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    int l = can - 1, r = n - can;
    while (l >= r) --l, ++r;
    if (best >= (sum + 1) / 2) {
      mn = min(mn, (long long)abs(can - (n - can)));
    }
  }
  // cout << "Minimum: " << mn << '\n';
  for (int can = 1; can <= n; ++can) {
    long long cur = 0;
    for (int i = 0; i < can; ++i) {
      cur += a[i].first;
    }
    long long lo = 1, hi = can, best = cur;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      int l = mid - 1, r = n - mid;
      if (l >= r) {
        hi = mid - 1;
        continue;
      }
      long long u = pref[l];
      long long v = pref[n - 1] - (!r ? 0 : pref[r - 1]);
      long long k = cur - u + v;
      if (k >= (sum + 1) / 2) {
        best = k;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    if (best >= (sum + 1) / 2) {
      if (mn == abs(can - (n - can))) {
        set<long long> s;
        cur = 0;
        for (int i = 0; i < can; ++i) {
          cur += a[i].first;
          s.insert(a[i].second);
        }
        long long l = 0, r = n - 1;
        while (l < can && l < r && cur < (sum + 1) / 2) {
          cur -= a[l++].first;
          cur += a[r--].first;
          s.erase(a[l - 1].second);
          s.insert(a[r + 1].second);
        }
        vector<int> ans;
        for (auto &i : s) {
          ans.push_back(i);
        }
        sort(ans.begin(), ans.end(), [&](int i, int j) {
          return A[i] < A[j];
        });
        for (int i = 0; i < n; ++i) {
          if (s.find(i) == s.end()) {
            ans.push_back(i);
          }
        }
        return ans;
      }
    }
  }
  return {-1};
}
