#include<bits/stdc++.h>
#include "partition.h"
using namespace std;
mt19937 rng(49282199);
std::vector<int> solve(std::vector<int> A) {

   int N = (int)A.size();
   int mid = (N - 1) / 2;

   vector<pair<int , int>> V;
   long long sum = 0;
   for(int i = 0;i < N;i ++){
      V.push_back({A[i] , i});
      sum += A[i];
   }
   for(int i = 1;i < N;i ++){
      swap(V[i] , V[rng() % i]);
   }
   nth_element(V.begin() , V.begin() + mid , V.end());

   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 <= mid + 1;l ++){
      if(sz == (N + 1) / 2){

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

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

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

         return ans;
      }

      s += V[l].first;
      sz++;

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

   }  
}
