#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<pair<ll, int>> A(n);
    vector<int> permutation(n);
    f(i, 0, n) permutation[i] = i;
    f(i, 0, n) A[i] = { wtf[i], i };
    //auto m = A.begin() + A.size() / 2;
    //std::nth_element(A.begin(), m, A.end());
    if(n < 1000) sort(A.begin(), A.end());
    else f(i, 0, n) if (A[i] > A[n - i]) swap(A[i], A[n - i]);
    ll sum = 0;
    f(i, 0, n) sum += A[i].first;
    ll req = (sum + 1) / 2;
    ll presum = 0;
    f(i, 0, (n+1) / 2) presum += A[i].first;
    int first = 0;
    int last = n - 1;
    while (presum < req) {
        presum += A[last].first;
        presum -= A[first].first;
        swap(A[last], A[first]);
        first++; last--;
    }
    if (first > 0) {
        first--;
        swap(A[(n - 2) / 2], A[first]);
    }
    f(i, 0, n) permutation[i] = A[i].second;
    return permutation;
}