#include<bits/stdc++.h>
#include "partition.h"
using namespace std;
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 ++){
      sum += A[i];
   }


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

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

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

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

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

         return ans;
      }

      s = s + A[l];

      while(r != N && s - A[r] >= sum - s + A[r]){
         s = s - A[r];
         r = r + 1;
      }
   }  

   r = N;
   s = 0LL;

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

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

         for(int i = 0;i < l;i ++){
            ans.push_back(N - i - 1);
         }

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

         for(int i = l;i < r;i ++){
            ans.push_back(N - i - 1);
         }

         return ans;
      }

      s += A[N - l - 1];

      while(r != N && s - A[N - r - 1] >= sum - s + A[N - r - 1]){
         s = s - A[N - r - 1];
         r = r + 1;
      }
   }  
}