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

   int N = (int)A.size();
   long long sum = accumulate(A.begin() , A.end() , 0LL);
   long long s = 0;
   int l = 0;
   for(int r = 0;r < N;r ++){
      s = s + A[r];
      while(sum - s + A[l] <= s - A[l]){
         s = s - A[l];
         l = l + 1;
      }
      if(sum - s <= s && r - l + 1 == (N + 1) / 2){
         vector<int> ans;
         for(int i = r;i >= l;i --){
            ans.push_back(i);
         }
         for(int i = 0;i < l;i ++){
            ans.emplace_back(i);
         }
         for(int i = r + 1;i < N;i ++){
            ans.emplace_back(i);
         }  
         return ans;
      }
   }

   int r = N - 1;
   s = 0;
   for(int l = N - 1;l >= 0;l --){
      s = s + A[l];
      while(sum - s + A[r] <= s - A[r]){
         s = s - A[r];
         r = r - 1;
      }
      if(sum - s <= s && r - l + 1 == (N + 1) / 2){
         vector<int> ans;
         for(int i = l;i <= r;i ++){
            ans.push_back(i);
         }
         for(int i = 0;i < l;i ++){
            ans.emplace_back(i);
         }
         for(int i = r + 1;i < N;i ++){
            ans.emplace_back(i);
         }  
         return ans;
      }
   }
}