#include "partition.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> solve(vector<int> A) {
    int n = A.size();
    vector<int> so;
    for (int i = 0; i < n; i++){
        so.push_back(i);
    }
    vector<int> us(n + 1, 0), ans;
    ll su = 0, go = 0, cnt = 0, sz = 0;
    for (int i = 0; i < n; i++){
        cnt++, su += A[i];
    }
    go = (su + 1) / 2, sz = (cnt + 1) / 2;
    ll cur = 0, cur2 = 0, l = 0, r = sz - 1;
    for (int i = 0; i < sz; i++){
        cur += A[i];
    }
    while (r < n && cur > go){
        l++, r++;
        cur = cur + A[r] - A[l - 1];
    }
    cur2 = cur;
    int le = l, ri = r;
    while (ri < n - 1 && cur2 < go){
        le++, ri++;
        cur2 = cur2 + A[r] - A[l - 1];
    }
    if (cur2 > go){
        for (int i = le; i <= ri; i++){
            ans.push_back(i);
            us[i] = 1;
        }
    }
    else{
        cur = cur;
        le = l, ri = r;
        while (le > 0 && cur2 < go){
            le--, ri--;
            cur2 = cur2 + A[le] - A[ri + 1];
        }
        if (cur2 > go) while (1) cur2++;
            for (int i = ri; i >= le; i--){
                ans.push_back(i);
                us[i] = 1;
            }
        }
    for (int i = 0; i < n; i++){
        if (us[i] == 0) ans.push_back(i);
    }
    return ans;
}
