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

std::vector<int> solve(std::vector<int> A) {
  int n = (int)A.size();
  map<int, deque<int>> idx;
  for (int i = 0; i < n; ++i) {
    idx[A[i]].push_back(i);
  }
  sort(A.begin(), A.end());
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += A[i];
  }
  int mn = n;
  for (int can = 1; can <= n; ++can) {
    int cur = 0;
    for (int i = 0; i < can; ++i) {
      cur += A[i];
    }
    if (cur > (sum + 1) / 2) {
      break;
    }
    int l = 0, r = n - 1;
    while (l < can && l < r) {
      cur -= A[l++];
      cur += A[r--];
      if (cur >= (sum + 1) / 2) {
        break;
      }
    }
    if (cur >= (sum + 1) / 2) {
      mn = min(mn, abs(can - (n - can)));
    }
  }
  // cout << "Minimum: " << mn << '\n';
  for (int can = 1; can <= n; ++can) {
    int cur = 0;
    for (int i = 0; i < can; ++i) {
      cur += A[i];
    }
    if (cur > (sum + 1) / 2) {
      break;
    }
    int l = 0, r = n - 1;
    while (l < can && l < r) {
      cur -= A[l++];
      cur += A[r--];
      if (cur >= (sum + 1) / 2) {
        break;
      }
    }
    if (cur >= (sum + 1) / 2) {
      if (mn == abs(can - (n - can))) {
        set<int> s;
        cur = 0;
        for (int i = 0; i < can; ++i) {
          cur += A[i];
          s.insert(i);
        }
        l = 0, r = n - 1;
        while (l < can && l < r) {
          cur -= A[l++];
          cur += A[r--];
          s.erase(l - 1);
          s.insert(r + 1);
          if (cur >= (sum + 1) / 2) {
            break;
          }
        }
        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};
}
