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

std::vector<int> solve(std::vector<int> A) {
  int n = (int)A.size();
  long long sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += A[i];
  }
  vector<int> idx(n);
  iota(idx.begin(), idx.end(), 0);
  long long ans = 1e9;
  do {
    long long cur = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
      cur += A[idx[i]];
      if (cur >= (sum + 1) / 2) {
        cnt = i + 1;
        break;
      }
    }
    ans = min(ans, (long long)abs(cnt - (n - cnt)));
  } while (next_permutation(idx.begin(), idx.end()));
  iota(idx.begin(), idx.end(), 0);
  do {
    long long cur = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
      cur += A[idx[i]];
      if (cur >= (sum + 1) / 2) {
        cnt = i + 1;
        break;
      }
    }
    if (abs(cnt - (n - cnt)) == ans) {
      return idx;
    }
  } while (next_permutation(idx.begin(), idx.end()));
  return {-1};
}
