#include "partition.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
#define f(i, s, n) for(int i=s; i<n; i++)

std::vector<int> solve(std::vector<int> wtf) {
    int n = wtf.size();
    vector<ll> A(n);
    vector<int> permutation(n);
    f(i, 0, n) permutation[i] = i;
    f(i, 0, n) A[i] = wtf[i];
    auto m = A.begin() + A.size() / 2;
    std::nth_element(A.begin(), m, A.end());
    ll sum = 0;
    f(i, 0, n) sum += A[i];
    ll req = (sum + 1) / 2;
    ll presum = 0;
    f(i, 0, n / 2) presum += A[i];
    int first = 0;
    int last = n - 1;
    while (presum < req) {
        presum += A[last];
        presum -= A[first];
        swap(A[last], A[first]);
        swap(permutation[last], permutation[first]);
        first++; last--;
    }
    first--;
    swap(A[n / 2], A[first]);
    swap(permutation[n / 2], permutation[first]);    

    return permutation;
}