#include "partition.h"
std::vector<int> solve(std::vector<int> A)
{
    int n = A.size();
    std::vector<std::pair<int,int>> pi;
    for(int i=0; i<A.size(); i++) pi.push_back({A[i],i});
    sort(pi.begin(),pi.end());
    //for(auto x:pi) cout<<x.first<<" "<<x.second<<endl;
    std::vector<int> ans;
    for(int i=0; i<n/2; i++) ans.push_back(pi[i].second);
    ans.push_back(pi[n-1].second);
    for(int i=n/2; i<n-1; i++) ans.push_back(pi[i].second);
    return ans;
}