#include <bits/stdc++.h>
#include "partition.h"
using namespace std;
vector<int>* copie;
static inline bool Cmp(int a, int b) {
    return (*copie)[a] > (*copie)[b];
}
vector<int> solve(vector<int> a) {
    unordered_map<int, int> ap;
    vector<int> part[2];
    for(int i = 0; i < a.size(); i++) {
        if(ap.count(a[i]) && -1 != ap[a[i]]) {
            part[0].push_back(ap[a[i]]);
            part[1].push_back(i);
            ap[a[i]] = -1;
        }
        else ap[a[i]] = i;
    }

    vector<int> ram;
    for(auto cur : ap) {
        if(-1 < cur.second) ram.push_back(cur.second);
    }

    copie = &a;
    sort(ram.begin(), ram.end(), Cmp);

    //cout << ram.size();
    part[0].push_back(ram[0]);

    for(int i = 1; i < ram.size(); i++) part[1].push_back(ram[i]);

    part[0].insert(part[0].end(), part[1].begin(), part[1].end());
    return part[0];
}
