#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> solve(std::vector<int> a) {
    vector<int> ans;
    int n = a.size();
    map<int, vector<int>> pos;
    for (int i = 0; i < n; i++) {
        pos[a[i]].push_back(i);
    }
    for (auto [x, v] : pos) {
        int k = v.size() / 2;
        while (v.size() > k) {
            ans.push_back(v.back());
            v.pop_back();
        }
    }
    for (auto [x, v] : pos) {
        while (v.size()) {
            ans.push_back(v.back());
            v.pop_back();
        }
    }
    return ans;
}
