#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 - 1 , sz = 0;
   long long s = 0;
   while(s < sum - s){
      s += V[r--].first;
      ++sz;
   }

   vector<int> ans;
   for(int l = -1;l < mid;l ++){
      if(sz == (N + 1) / 2){
         assert(s >= sum - s);
         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 + 1;i <= r;i ++){
            ans.emplace_back(V[i].second);
         }
         break;
      }

      if(l == -1){
         continue;
      }

      sz += 1;
      s += V[l].first;
      while(r != N - 1 && !((s - V[r + 1].first) < sum - (s - V[r + 1].first))){
         --sz;
         s -= V[r + 1].first;
         r += 1;
      }
   }
   assert((int)ans.size() == N);
   return ans;
}

