#include<bits/stdc++.h>
#include "partition.h"
using namespace std;
std::vector<int> solve(std::vector<int> A) {
   int N = (int)A.size();
   // vector<int> o(N);
   // iota(o.begin() , o.end() , 0);
   // sort(o.begin() , o.end() , [&](int i , int j){
   //    return A[i] > A[j];
   // });

   int mid = (N - 1) / 2;

   vector<pair<int , int>> V;
   for(int i = 0;i < N;i ++){
      V.push_back({A[i] , i});
   }

   nth_element(V.begin() , V.begin() + mid , V.end());
   long long sum = accumulate(A.begin() , A.end() , 0LL);

   int r = N , sz = 0;
   long long s = 0;
   while(s < sum - s){
      s += V[--r].first;
      sz += 1;
   }

   vector<int> ans;
   for(int l = 0;l <= min(N - 1 , mid + 1);l ++){
      if(sz == (N + 1) / 2){

         for(int i = 0;i < l;i ++){
            ans.emplace_back(V[i].second);
         }

         for(int i = N - 1;i >= r;i --){
            ans.emplace_back(V[i].second);
         }

         for(int i = l;i < r;i ++){
            ans.emplace_back(V[i].second);
         }

         break;
      }


      if(l >= 0){
         s += V[l].first;
         sz++;

         while(r != N && s - V[r].first >= sum - s + V[r].first){
            s -= V[r++].first;
            sz -= 1;
         }

      }

   }  

   assert((int)ans.size() == N);
   return ans;
}
