#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <iterator>
#include <cassert>
#include <queue>
#include "partition.h"
using namespace std;

#define dbg(x) cerr << #x << ' '; print(x); cerr << endl;
void print(int x) { cerr << x; }
void print(long long x) { cerr << x; }
void print(char x) { cerr << x; }
void print(string x) { cerr << x; }
void print(double x) { cerr << x; }
template <class T, class V> void print(pair <T, V> x);
template <class T> void print(vector <T> x) { cerr << "[ "; for (T i : x) { print(i); cerr << ' '; } cerr << ']'; }
template <class T> void print(set <T> x) { cerr << "[ "; for (T i : x) { print(i); cerr << ' '; } cerr << ']'; }
template <class T> void print(multiset <T> x) { cerr << "[ "; for (T i : x) { print(i); cerr << ' '; } cerr << ']'; }
template <class T, class V> void print(pair <T, V> x) { cerr << "{"; print(x.first); cerr << ' '; print(x.second); cerr << "}"; }

#define ll long long
#define OK cerr << "OK\n"
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define PII pair <int, int>
#define MP make_pair
#define inf 1e9 + 5
#define inf64 1e18 + 5;
#define pb push_back

int n;
vector <PII> a;

vector<int> solve(vector<int> A) {
	n = A.size();
	for (int i = 0; i < n; i++) {
		a.pb({ A[i], i });
	}
	sort(all(a));
	int r = 0, cnt = 0;
	vector <int> answs, answv;
	//dbg(a);
	for (int i = 0; i < n; i++) {
		//dbg(r);
		if (!i) {
			cnt++;
			continue;
		}
		if (a[i].first != a[i - 1].first) {
			int curr_cnt = 0;
			for (int j = r; j < i; j++) {
				if (curr_cnt < cnt / 2) {
					answs.pb(a[j].second);
					curr_cnt++;
				}
				else {
					answv.pb(a[j].second);
				}
			}
			cnt = 1, r = i;
		}
		else {
			cnt++;
		}
	}
	int curr_cnt = 0;
	for (int j = r; j < n; j++) {
		if (curr_cnt < cnt / 2) {
			answs.pb(a[j].second);
			curr_cnt++;
		}
		else {
			answv.pb(a[j].second);
		}
	}

	vector <int> answ;
	assert(answs.size() == answv.size());
	for (int i : answs) answ.pb(i);
	for (int i : answv) answ.pb(i);
	return answ;
}