#include "partition.h"
#include <algorithm>

using namespace std;
typedef long long ll;

vector<int> solve(vector<int> a) {
    int n = a.size();
  
    int n1 = (n + 1) / 2;
    int n2 = n / 2;

    ll s = 0;
    for (int i = 0; i < n; ++i) {
        s += a[i];
    }
    s = (s + 1) / 2;

    ll s1 = 0;
    for (int i = 0; i < n2; ++i) {
        s1 += a[i];
    }

    bool fl = (s1 >= s);

    if (fl) {
        vector<int> b(n);
        for (int i = 0; i < n2; ++i) {
            b[i] = a[i + n1];
        }
        for (int i = 0; i < n1; ++i) {
            b[i + n2] = a[i];
        }
        for (int i = 0; i < n; ++i) {
            a[i] = b[i];
        }
    }

    vector<ll> pr(n + 1, 0);
    for (int i = 0; i < n; ++i){
        pr[i + 1] = pr[i] + a[i];
    }

    vector<int> res;
    for (int r = n1; r <= n; ++r) {
        if (pr[r] - pr[r - n1] >= s) {
            for (int i = r - n1; i < r; ++i) {
                res.push_back(i);
            }
            for (int i = 0; i < r - n1; ++i) {
                res.push_back(i);
            }
            for (int i = r; i < n; ++i) {
                res.push_back(i);
            }
            break;
        }
    }
    if (fl) {
        for (int i = 0; i < n; ++i) {
            if (res[i] < n2) {
                res[i] = res[i] + n1;
            }
            else {
                res[i] = res[i] - n2;
            }
        }
    }
    return res;
}

