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

using namespace std;
typedef long long ll;

vector<int> solve(vector<int> a) {
    int n = a.size();
    vector<pair<int, int>> p(n);
    for (int i = 0; i < n; ++i) {
        p[i] = { a[i], i };
    }
  
    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];
    }
    if (s1 >= s) {
        p.clear();
        for (int i = 0; i < n2; ++i) {
            p.emplace_back(a[i + n1], i + n1);
        }
        for (int i = 0; i < n1; ++i) {
            p.emplace_back(a[i], i);
        }
        for (int i = 0; i < n; ++i) {
            a[i] = p[i].first;
        }
    }


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

    for (int r = n1; r <= n; ++r) {
        if (pr[r] - pr[r - n1] >= s) {
            vector<int> res;
            for (int i = r - n1; i < r; ++i) {
                res.push_back(p[i].second);
            }
            for (int i = 0; i < r - n1; ++i) {
                res.push_back(p[i].second);
            }
            for (int i = r; i < n; ++i) {
                res.push_back(p[i].second);
            }
            return res;
        }
    }
    return a;
}

