#include <iostream>
#include <string>
#include <vector>
#include "partition.h"
#include <algorithm>
using namespace std ;
vector<int> solve(std::vector<int> a){
    int n = a.size();
    vector<pair<int,int>> b;
    int sumt=0;
    for (int i=0; i<n;i++){
        b.push_back({a[i],i});
        sumt+=a[i];

    }
    sort(b.begin(),b.end());
    int sum=0;
    int i=0;
    int mid =n/2;
    while (i*2<n){
       
        sum+= b[i].first;
        i++;

    }
    int j=0;
    while (sum*2 <sumt ){
        sum-=a[i];
        sum +=a[n-j-1];
        j++;

    }
    vector<int> finale(n);
    for (int k=0; k<=mid;k++){
        if (k<j){
            finale[mid+k+1]=b[k].second;
        }
        else{
            finale[k-j]=b[k].second;
        }
    }
  
    for (int k=n;n-k<j;k--){
        finale[k-mid-1]=b[k-1].second;
    }
    for (int k=n-j-1;k>mid;k--){
        finale[k+j]=b[k].second;
    }
    return finale;
    

}
signed main(){
    vector<int> sol=solve((vector<int>){5 ,6 ,6, 3 ,1, 1, 4, 4, 3});
    for (int i=0; i<sol.size();i++){
        cout<< sol[i]<<" ";
    }
    
}