#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 = accumulate(A.begin() , A.end() , 0LL);
   long long s = 0;
   int l = 0;
   for(int r = 0;r < N;r ++){
      s += A[r];
      while(s - A[l] >= sum - s + A[l]){
         s -= A[l];
         l = l + 1;
      }
      if(s >= sum - s && r - l + 1 == (N + 1) / 2 && s - max(A[l] , A[r]) < sum - s + max(A[l] , A[r])){
         vector<int> ans;
         if(A[l] <= A[r]){
            for(int i = l;i <= r;i ++){
               ans.emplace_back(i);
            }
         }else{
            for(int i = r;i >= l;i --){
               ans.emplace_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;
      }
   }
}
