#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 r1 = N , r2 = N;
   long long s1 = 0 , s2 = 0;
   while(s1 < sum - s1){
      r1 = r1 - 1;
      s1 += A[r1];
   }

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

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

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

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

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

         return ans;
      }

      if(l + N - r2 == (N + 1) / 2){

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

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

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

         return ans;
      }

      s1 = s1 + A[l];
      s2 = s2 + A[l];

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

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

