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

using namespace std;

int n;
deque <int> dq;
map <int, vector <int>> umap;
vector<int> solve(vector<int> A) {
    // v.clear();
    umap.clear();
    while(!dq.empty())
        dq.pop_back();

    n = A.size();
    for(int i = 0; i < n; i++)
        umap[A[i]].push_back(i);
    for(auto var : umap) {
        for(int i = 0; i < var.second.size(); i += 2) {
            dq.push_back(var.second[i]);
            dq.push_front(var.second[i + 1]);
        }
    }
    vector <int> ans;
    while(!dq.empty()) {
        ans.push_back(dq.front());
        dq.pop_front();
    }
    return ans;
}