#include "partition.h"
#include <algorithm>
using namespace std;
vector<int> a;
bool cmp(int x,int y)
{
    return a[x]<a[y];
}
int n;
std::vector<int> solve(std::vector<int> A)
{
    a=A;
    n=a.size();
    vector<int> idx;
    for(int i=0; i<a.size(); i++)
    {
        idx.push_back(i);
    }
    sort(idx.begin(),idx.end(),cmp);
    idx.push_back(n);
    a.push_back(-1);
    vector<int> ans1,ans2,ans3;
    int cnt=0;
    int px=a[idx[0]];
    for(int i=0; i<idx.size(); i++)
    {
        if(a[idx[i]]==px)cnt++;
        else
        {
            for(int j=0; j<cnt-cnt%2; j++)
            {
                if(j%2==0)
                {
                    ans1.push_back(idx[i-j]);
                }
                else
                {
                    ans2.push_back(idx[i-j]);
                }
            }
            if(cnt%2==1)
                ans3.push_back(i-cnt);
            px=idx[i];
            cnt=1;
        }
    }
    {
        int sz=ans3.size();
        for(int i=0; i<(sz-1)/2; i++)
        {
            ans1.push_back(ans3[i]);
        }
        ans1.push_back(ans3.back());
        for(int i=(sz-1)/2; i<sz-1; i++)
        {
            ans2.push_back(ans3[i]);
        }

    }
    for(int x:ans2)ans1.push_back(x);
    return ans1;
}
