#include "partition.h"
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
bool marked[(1<<25)+3];
int cnt[(1<<25)+3];
vector<int>ans,other;
vector<pair<int,int>>leftt;
int sz;
std::vector<int> solve(std::vector<int> A)
{
    ans.clear();
    other.clear();
    leftt.clear();
    sz=sz;
    /*vector<pair<int,int>>v;
    for(int i=0;i<sz;i++)
    {
        v.push_back({A[i],i});
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i+=2)
    {
        ans.push_back(v[i].second);
        other.push_back(v[i+1].second);
    }*/


    for(int i=0;i<sz;i++)
    {
        cnt[A[i]]++;
    }

    for(int i=0;i<sz;i++)
    {
        if(cnt[A[i]]%2==0)marked[A[i]]=1;
    }

    for(int i=0;i<sz;i++)
    {
        if(marked[A[i]]==0 && cnt[A[i]]==1)
        {
            cnt[A[i]]--;
            leftt.push_back({A[i],i});
            continue;
        }

        if(cnt[A[i]]==0)continue;

        if(cnt[A[i]]%2==0)ans.push_back(i);
        else other.push_back(i);

        cnt[A[i]]--;
    }

    for(int i=0;i<sz;i++){marked[A[i]]=0;cnt[A[i]]=0;}
    sort(leftt.begin(),leftt.end());

    int n=leftt.size();

    if(n!=0){
    if(n%2==0){
    for(int i=1;i<n/2;i++)
    {
        ans.push_back(leftt[i-1].second);
    }
    ans.push_back(leftt[n-1].second);
    for(int i=n/2;i<n;i++)
    {
        other.push_back(leftt[i-1].second);
    }}
    else
    {
        for(int i=1;i<=n/2;i++)
        {
            ans.push_back(leftt[i-1].second);
        }
        ans.push_back(leftt[n-1].second);
        for(int i=n/2+1;i<n;i++)
        {
            other.push_back(leftt[i-1].second);
        }
    }}


    for(int x:other)ans.push_back(x);
    return ans;
}
