#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<pair<int, int>> a;
    for(int i = 0; i < A.size(); i++) {
        a.push_back({A[i], i});
    }
  //  sort(a.begin(), a.end());
    int l = 0, r = 0;
    LL s1 = 0, ds = s / 2 + s % 2;
    for(r; r < a.size(); r++) {
        s1 += a[r].first;
        if(s1 >= ds) break;
    }
   // cout << l << " " << r << " " << s1 << endl;
    int minr = abs((int)a.size() - 2 * (r + 1)), l1 = 0, r1 = r;
    for(++r; r < a.size(); r++) {
        s1 += a[r].first;
        while(s1 - a[l].first >= ds && l <= r) {
            s1 -= a[l].first;
            l++;
        }
        if(s1 - a[l].first >= ds) l--;
        if(l > r) continue;
      //  cout << l << " " << r << " " << s1 << endl;
        if(s1 >= ds) {
            if(minr > abs((int)a.size() - 2 * (r - l + 1))) {
                minr = abs((int)a.size() - 2 * (r - l + 1));
                l1 = l, r1 = r;
            }
        }
    }
 //   cout << minr << endl;

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

