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

bool rdm;

pi kth(vector<pi> t, int k) {
    int n = t.size();
    pi pivot = t[1942834 % n];
    vector<pi> big;
    vector<pi> small;
    f(i, 0, n) {
        if (t[i] < pivot) small.push_back(t[i]);
        else if (pivot < t[i]) big.push_back(t[i]);
        /*else {
            if (rdm) small.push_back(t[i]);
            else big.push_back(t[i]);
            rdm = !rdm;
        }*/
    }
    if (small.size() >= k) return kth(small, k);
    if (small.size() < k - 1) return kth(big, k - small.size() - 1);
    return pivot;
}

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 };
    pi median = kth(A, (n+1) / 2);
    vector<pi> B;
    f(i, 0, n) if (A[i] < median) B.push_back(A[i]);
    B.push_back(median);
    f(i, 0, n) if (A[i] > median) B.push_back(A[i]);
    swap(A, B);
    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;
}