#include "partition.h"
#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e18;

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

    bool sub1 = ~int(B.size()) & 1;
    sort(B.begin(), B.end());
    for (int i = 1; i < (int)B.size(); i += 2) {
        sub1 = (B[i] != B[i - 1] ? 0 : sub1);
    }

    bool sub2 = 1;
    for (int i = 0; i < (int)A.size(); ++i) {
        sub2 = (A[i] != (1 << i) ? 0 : sub2);
    }

    bool sub3 = 1;
    for (int i = 0; i < (int)A.size(); ++i) {
        sub3 = ((A[i] & (A[i] - 1)) ? 0 : sub3);
    }

    if (sub1) {
        vector<pair<int, int>> Ap;

        for (int i = 0; i < n; ++i) {
            Ap.push_back({A[i], i});
        }

        sort(Ap.begin(), Ap.end());

        vector<int> ans;
        for (int i = 0; i < n; i += 2) {
            ans.push_back(Ap[i].second);
        }

        for (int i = 1; i < n; i += 2) {
            ans.push_back(Ap[i].second);
        }

        return ans;
    } else if (sub2) {
        vector<int> ans;
        for (int i = 0; i < (n - 1) / 2; ++i) {
            ans.push_back(i);
        }
        ans.push_back(n - 1);

        for (int i = (n - 1) / 2; i < n - 1; ++i) {
            ans.push_back(i);
        }

        return ans;
    } else {
        vector<pair<int, int>> Ap;

        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            Ap.push_back({A[i], i});
            sum += A[i];
        }

        sort(Ap.begin(), Ap.end());

        vector<long long> suff(n + 1);
        for (int i = n - 1; i >= 0; --i) {
            suff[i] = Ap[i].first + suff[i + 1];
        }

        auto check = [&](long long cur, int ptr) {
            int l = ptr + 1, r = n;
            while (r - l > 1) {
                int m = (l + r) >> 1;

                if (cur + suff[m] >= (sum + 1) / 2) {
                    l = m;
                } else {
                    r = m;
                }
            }

            int fp = n - l + ptr + 1;
            int sp = n - fp;

            return abs(fp - sp);
        };

        int mn = n + 1, mni = -1;
        long long pref = 0;

        if (mn > check(pref, -1)) {
            mn = check(pref, -1);
            mni = -1;
        }

        for (int i = 0; i < n; ++i) {
            pref += Ap[i].first;
            if (mn > check(pref, i)) {
                mn = check(pref, i);
                mni = i;
            }
        }

        vector<int> ans;
        pref = 0;

        for (int i = 0; i <= mni; ++i) {
            ans.push_back(Ap[i].second);
            pref += Ap[i].first;
        }

        int l = mni + 1, r = n;
        while (r - l > 1) {
            int m = (l + r) >> 1;

            if (pref + suff[m] >= (sum + 1) / 2) {
                l = m;
            } else {
                r = m;
            }
        }

        for (int i = l; i < n; ++i) {
            ans.push_back(Ap[i].second);
        }

        for (int i = mni + 1; i < l; ++i) {
            ans.push_back(Ap[i].second);
        }

        return ans;
    }

    return {};
}
