#include "partition.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

vector<int> solve(vector<int> v) {
    int n = v.size();
    vector <int> ans;

    bool ok1 = true, ok2 = true;
    for (int i = 0; i < n; i++) {
        if (v[i] != (1 << i)) {
            ok1 = false;
        }

        if (v[i] != i + 1) ok2 = false;
    }

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

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

        return ans;
    }

    if (ok2 == true) {
        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;
    }

    vector <int> ramase;
    map <int, int> fr;

    for (int i = 0; i < n; i++) {
        if (fr[v[i]] % 2 == 0) ans.push_back(i);
        else ramase.push_back(i);

        fr[v[i]]++;
    }

    for (auto it : ramase) {
        ans.push_back(it);
    }

    return ans;
}


