#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> 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){
        if (cur >= go && cur - max(A[l], A[r]) < go){
            if (cur - A[r] < go){
                for (int i = l; i <= r; i++){
                    ans.push_back(i);
                    us[i] = 1;
                }
            }
            else{
                for (int i = r; i >= l; i--){
                    ans.push_back(i);
                    us[i] = 1;
                }
            }
            break;
        }
        l++, r++;
        if (r < n) cur = cur + A[r] - A[l - 1];
    }
    for (int i = 0; i < n; i++){
        if (us[i] == 0) ans.push_back(i);
    }
    return ans;
}
