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

std::vector<int> solve(std::vector<int> a) {
    int n = int(a.size());
    std::map<int, std::vector<int>> mp;
    for(int i = 0; i < n; i++) {
        mp[a[i]].push_back(i);
    }
    std::vector<int> sol;
    for(auto& [val, p] : mp) {
        int sz = int(p.size());
        for(int i = 0; i < sz / 2; i++) {
            sol.push_back(p[i]);
        }
    }
    for(auto& [val, p] : mp) {
        int sz = int(p.size());
        for(int i = sz / 2; i < sz; i++) {
            sol.push_back(p[i]);
        }
    }
    return sol;
}
