#include "partition.h"
#include <algorithm>
#include <iostream>
#pragma GCC target("avx2")

const int MASK = 40;

using ll = long long;

int n;
int fr[MASK + 10];
void radix(const std::vector<int> & A, std::vector<int> &ind) {
    std::vector<int> B(n);

    for (int iter = 0; iter < 1; iter++) {
        for (int i = 0; i <= MASK; i++)
            fr[i] = 0;

        for (int i = 0; i < n; i++) {
            fr[31 - __builtin_clz(A[i])]++;
        }

        for (int i = 1; i <= MASK; i++)
            fr[i] += fr[i - 1];

        for (int i = n - 1; i >= 0; i--) {
            B[--fr[31 - __builtin_clz(A[i])]] = ind[i];
        }

        for (int i = 0; i < n; i++)
            ind[i] = B[i];

    }
}

std::vector<int> solve(std::vector<int> A) {
    n = A.size();

    ll sum_total = 0;
    std::vector<int> ind(n);

    for (int i = 0; i < n; i++) {
        sum_total += A[i];
        ind[i] = i;
    }

    radix(A, ind);

    ll sum_first_half = 0;
    for (int i = 0; i < (n + 1) / 2; i++)
        sum_first_half += A[ind[i]];

    int idx = 0;

    while (sum_first_half + sum_first_half < sum_total) {
        sum_first_half += A[ind[n - 1 - idx]] - A[ind[idx]];
        std::swap(ind[idx], ind[n - 1 - idx]);
        idx++;
    }

    std::vector<int> ans;
    ans.reserve(n);

    for (int i = idx; i < (n + 1) / 2; i++)
        ans.push_back(ind[i]);
    for (int i = idx - 1; i >= 0; i--)
        ans.push_back(ind[i]);
    for (int i = (n + 1) / 2; i < n; i++)
        ans.push_back(ind[i]);

    return ans;
}
