#include "partition.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

vector<int> solve(vector<int> A)
{
    ll s = 0;
    for (auto it : A)
        s += it;
    vector<ll> sp(A.size());
    sp[0] = A[0];
    for (int i = 1; i < sp.size(); i++)
        sp[i] = sp[i - 1] + A[i];
    int nec = 0;
    ll sm = 0;
    for (int i = -1; i < (int)A.size(); i++)
    {
        if (i != -1)
            sm += A[i];
        if (2ll * sm >= s)
        {
            int x = i + 1, y = A.size() - x;
            if (abs(x - y) <= 1)
            {
                vector<int> ha;
                for (int j = 0; j < A.size(); j++)
                    ha.push_back(j);
                return ha;
            }
            break;
        }
        else
        {
            while (nec + 1 < A.size())
            {
                if (2ll * (sm + sp[A.size() - 1] - sp[nec]) >= s)
                    nec++;
                else
                    break;
            }
            //cout << i << ' ' << nec << endl;
            int x = i + 1 + (int)A.size() - nec;
            int y = (int)A.size() - x;
            if (abs(x - y) <= 1)
            {
                vector<int> ord;
                for (int j = 0; j <= i; j++)
                    ord.push_back(j);
                for (int j = A.size() - 1; j >= nec; j--)
                    ord.push_back(j);
                for (int j = i + 1; j < nec; j++)
                    ord.push_back(j);
                //chk(ord);
                ll smm = 0;
                int xx = 0;
                for (auto it : ord)
                {
                    xx++;
                    smm += A[it];
                    if (2ll * smm >= s)
                        break;
                }
                if (xx != x)
                    assert(false);
                return ord;
            }
        }
    }
    reverse(A.begin(), A.end());
    int nn = A.size() - 1;
    sm = 0;
    nec = 0;
    sp[0] = A[0];
    for (int i = 1; i < A.size(); i++)
        sp[i] = sp[i - 1] + A[i];
    for (int i = -1; i < (int)A.size(); i++)
    {
        if (i != -1)
            sm += A[i];
        if (2ll * sm >= s)
        {
            int x = i + 1, y = A.size() - x;
            if (abs(x - y) <= 1)
            {
                vector<int> ha;
                for (int j = 0; j < A.size(); j++)
                    ha.push_back(nn - j);
                return ha;
            }
            break;
        }
        else
        {
            while (nec + 1 < A.size())
            {
                if (2ll * (sm + sp[A.size() - 1] - sp[nec]) >= s)
                    nec++;
                else
                    break;
            }
            //cout << i << ' ' << nec << endl;
            int x = i + 1 + (int)A.size() - nec;
            int y = (int)A.size() - x;
            if (abs(x - y) <= 1)
            {
                vector<int> ord;
                for (int j = 0; j <= i; j++)
                    ord.push_back(nn - j);
                for (int j = A.size() - 1; j >= nec; j--)
                    ord.push_back(nn - j);
                for (int j = i + 1; j < nec; j++)
                    ord.push_back(nn - j);
                //chk(ord);
                ll smm = 0;
                int xx = 0;
                for (auto it : ord)
                {
                    xx++;
                    smm += A[nn - it];
                    if (2ll * smm >= s)
                        break;
                }
                if (xx != x)
                    assert(false);
                return ord;
            }
        }
    }
    while(true);
}
