#include "partition.h"
#include <algorithm>
#include <iostream>
std::vector<int> solve(std::vector<int> A) {
    int s=0;
    std::vector<std::pair<int,int>>v;
    int n=0;
    for(int i=0;i<A.size();i++){
        int e=A[i];
        v.push_back({e,n});
        n++;
        s+=e;
    }
    std::sort(v.begin(),v.end(),[](std::pair<int,int> a,std::pair<int,int> b){
        return a.first<b.first;
    });
    std::vector<int>ans;
    for(int i=0;i<n;i++){
        ans.push_back(0);
    }
    int cnt=1;
    int nr=0;
    ans[0]=v[n-1].second;
    for(int i=n-2;i>=0;i--){
        if(v[i].first==v[i+1].first){
            cnt++;
            if(i%2==(n-1)%2) ans[nr]=v[i].second;
            else ans[n-nr-1]=v[i].second,nr++;
        }
        else if(cnt%2==0){
            cnt=1;
            if(i%2==(n-1)%2) ans[nr]=v[i].second;
            else ans[n-nr-1]=v[i].second,nr++;
        }
        else{
            ans[nr]=v[i].first;
            break;
        }
    }
    /**
    int sum=0;
    for(int i=0;i<n/2;i++){
        ans.push_back(v[i].second);
        sum+=v[i].first;
    }
    ans.push_back(v[n].second);
    sum+=v[n].first;
    for(int i=n/2;i<n;i++){
        ans.push_back(v[i].second);
    }
    **/
    return ans;
}
