#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> solve(vector<int> a) {
  int n = a.size();
  map<int, vector<int>> tr;
  for (int i = 0; i < n; i++) {
    if (tr.count(a[i])) {
      tr[a[i]].push_back(i);
    } else {
      tr[a[i]] = {i};
    }
  }
  vector<int> ans(n);
  int j1 = 0, j2 = n / 2;
  for (auto [x, b] : tr) {
    for (int i = 0; i < b.size(); i++) {
      if (i < b.size() / 2) {
        ans[j1] = b[i];
        j1++;
      } else {
        ans[j2] = b[i];
        j2++;
      }
    }
  }
  return ans;
}
