#include "partition.h"
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
std::vector<int> solve(std::vector<int> A)
{
    unordered_map<int,int> frec;
    vector<int> ans1;
    vector<int> ans2;
    vector<pair<int,int>> a;
    int cnt=0;
    for(int i=0; i<A.size(); i++)
    {
        frec[A[i]]++;
        if(frec[A[i]]%2==0)
        {
            cnt+=frec[A[i]];
        }
        else
        {
            cnt-=frec[A[i]];
            cnt++;
        }
        a.push_back({A[i],i});
    }
    if(cnt==A.size()-1)
    {
        for(int i=0; i<A.size(); i+=2)
        {
            ans2.push_back(i);
        }
        for(int i=1; i<A.size(); i+=2)
        {
            ans2.push_back(i);
        }
        return ans2;
    }else{
    vector<pair<int,int>> v1,v2;
    long long sumtot=0,sumv2=0;
    sort(a.begin(),a.end());
    int last=0;
    for(int i=0; i<a.size()/2-1; i++)
    {
        sumtot+=a[i].first;
        v1.push_back(a[i]);
    }
    v1.push_back(a[A.size()/2-1]);
    sumtot+=a[A.size()/2-1].first;
    for(int i=A.size()/2; i<A.size(); i++)
    {
        sumtot+=a[i].first;
        sumv2+=a[i].first;
        v2.push_back(a[i]);
    }
    bool ok=0;
    while(!v1.empty() && !v2.empty())
    {
        pair<int,int> it=*v1.begin();
        pair<int,int> it2=*v2.begin();
        if(sumv2-A[it2.second]+A[it.second]>sumtot/2)
        {
            v2.erase(v2.begin());
            v1.erase(v1.begin());
            ans2.push_back(it.second);
            v1.push_back(it2);
            sumv2=sumv2-A[it2.second]+A[it.second];
        }
        else
        {
            ans1.push_back(it.second);
            v1.erase(v1.begin());
        }
    }
    while(!v2.empty())
    {
        pair<int,int> it=*v2.begin();
        ans2.push_back(it.second);
        v2.erase(v2.begin());
    }
    while(!v1.empty())
    {
        pair<int,int> it=*v1.begin();
        ans1.push_back(it.second);
        v1.erase(v1.begin());
    }
    for(int i=0; i<ans1.size(); i++)
    {
        ans2.push_back(ans1[i]);
    }
    return ans2;
    }
}

