#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);
    }

    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;
    }

    return {};
}
