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

   int N = (int)A.size();
   int mid = (N - 1) / 2;
   long long sum = 0;
   for(int i = 0;i < N;i ++){
      V[i] = i;
      sum += A[i];
   }

   // nth_element(V , V + mid , V + N , [&](int i , int j){
   //    return A[i] < A[j];
   // });

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

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

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

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

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

         return ans;
      }

      s = s + A[V[l]];
      sz = sz + 1;

      while(s - A[V[r]] >= sum - s + A[V[r]]){
         s = s - A[V[r++]];
         sz = sz - 1;
      }
   }  

   reverse(V , V + N);

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

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

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

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

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

         return ans;
      }

      s = s + A[V[l]];
      sz = sz + 1;

      while(s - A[V[r]] >= sum - s + A[V[r]]){
         s = s - A[V[r++]];
         sz = sz - 1;
      }
   }  
}