#include<bits/stdc++.h>
#include "partition.h"
using namespace std;
const int MAX = 2E6;
pair<int , int> V[MAX];
std::vector<int> solve(std::vector<int> A) {

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

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


   nth_element(V , V + mid , V + N);

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

   A.clear();
   for(int l = 0;l <= mid + 1;l ++){
      if(sz == (N + 1) / 2){

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

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

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

         return A;
      }

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

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

   }  
}
