#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

vector<int> solve(vector<int> A) {
    LL s = 0;
    for(int ch : A) s += (LL)ch;
    vector<int> pr = {0};
    LL k = 0;
    for(int i = 0; i < A.size(); i++) {
        k += A[i], pr.push_back(k);
    }
  //  sort(a.begin(), a.end());
    LL s1 = 0, ds = s / 2 + s % 2;
    int minr = INT_MAX, l1, r1;
    for(int i = 0; i < A.size(); i++) {
        int l = 0, r = i, mid, jk = -1;
        while(l <= r) {
            mid = (l + r) >> 1;
            if(pr[i + 1] - pr[mid] >= ds) {
                jk = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        if(jk == -1) continue;
      //  cout << l << " " << r << " " << s1 << endl;

        if(minr > abs((int)A.size() - 2 * (i - jk + 1))) {
                minr = abs((int)A.size() - 2 * (i - jk + 1));
                l1 = jk, r1 = i;
        }

    }
   // cout << minr << endl;

    vector<int> ans;
    for(int i = l1; i <= r1; i++) {
        ans.push_back(i);
    }
    for(int i = 0; i < l1; i++) {
        ans.push_back(i);
    }
    for(int i = r1 + 1; i < A.size(); i++) {
        ans.push_back(i);
    }
    return ans;
}

