#define ll long long

#include "partition.h"
#include<bits/stdc++.h>
using namespace std;

const ll MAXN=2e6+3;
ll n;
//pair<ll,ll> a[MAXN];
map<ll,vector<ll> > indx;

vector<int> solve(vector<int> a)
{
    n=a.size();
    bool f=0;
    for(ll i=0;i<n;i++){
        if(!indx[a[i]].empty()) f=1;
        indx[a[i]].push_back(i);

    }
    if(f==0){
        ll ma=0,maindx;
    for(ll i=0;i<n;i++){
        if(a[i]>ma){ma=a[i]; maindx=i;}
    }

    vector<int> ans(n,0);
    for(ll i=0;i<n;i++) ans[i]=i;
    swap(ans[maindx],ans[(n-1)/2]);
    return ans;
    }

    vector<int> ans(n,0);
    ll l=0,r=n-1,sz;
    vector<ll> ost;
    for(auto tv : indx){
        auto v=tv.second;
        sz=v.size();
        if(sz%2==0){
            for(ll i=0;i<sz;i++){
                if(i%2==0) ans[l++]=v[0];
                else ans[r--]=v[0];
            }
        }
        else{
            ost.push_back(v[sz-1]);
            for(ll i=0;i<sz-1;i++){
                if(i%2==0) ans[l++]=v[0];
                else ans[r--]=v[0];
            }
        }
    }

    ll ma=0,maindx;
    for(ll i=0;i<ost.size();i++){
        if(a[ost[i]]>ma){ma=a[ost[i]]; maindx=ost[i];}
    }

    ll k;
    for(ll i=0;i<ost.size();i++){
        ans[l+i]=ost[i];
        if(ost[i]==maindx) k=l+i;
    }

    swap(ans[k],ans[(n-1)/2]);
    return ans;
}
