#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());
  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 l = 0, r = n - 1;
    while (l < can && l < r && cur < (sum + 1) / 2) {
      cur -= a[l++].first;
      cur += a[r--].first;
    }
    if (cur >= (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 l = 0, r = n - 1;
    while (l < can && l < r && cur < (sum + 1) / 2) {
      cur -= a[l++].first;
      cur += a[r--].first;
    }
    if (cur >= (sum + 1) / 2) {
      if (mn == abs(can - (n - can))) {
        // cout << "Candidate:" << ' ' << can << '\n';
        set<long long> s;
        cur = 0;
        for (int i = 0; i < can; ++i) {
          cur += a[i].first;
          s.insert(a[i].second);
        }
        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);
        }
        for (int i = 0; i < n; ++i) {
          if (s.find(i) == s.end()) {
            ans.push_back(i);
          }
        }
        return ans;
      }
    }
  }
  return {-1};
}
