#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN=2*1e6;//1e6*2+1
const int MAXA=1e9+1;
int n;
bool visited[MAXN];
pair<vector<int>,int>cr[MAXA];
std::vector<int> solve(std::vector<int> a) {
    n=a.size();
    std::vector<int>ans;
    std::vector<int>d;
    for(int i=0;i<n;i++)
    {
        cr[a[i]].second++;
        cr[a[i]].first.push_back(i);
    }
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<": "<<cr[a[i]].second<<" status: "<<visited[a[i]]<<endl;
        if(visited[a[i]])continue;
        else visited[a[i]]=1;
           for(int j=0; j<cr[a[i]].second/2;j++)
           {
               ans.push_back(cr[a[i]].first[j]);
           }

           for(int j=cr[a[i]].second/2;j<cr[a[i]].second;j++)
           {
               d.push_back(cr[a[i]].first[j]);

           }

    }
    for(int i=0;i<d.size();i++)ans.push_back(d[i]);
    return ans;
}
