#include<bits/stdc++.h>
#include "partition.h"
#define endl "\n"
using namespace std;
void speed()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

bool cmp(pair<int, int> x, pair<int, int> y)
{
    return x.first < y.first;
}
vector<int> solve(vector<int> A)
{
    int n = A.size();
    vector<pair<int, int> > a(n);

    if(n == 1)
    {
        return {0};
    }
    else if(n == 2)
    {
        return {1, 0};
    }
    for(int i = 0; i < n; i++)
    {
        a[i].first = A[i];
        a[i].second = i;
    }
    vector<int> ans(n, -1);
    int SUM = n * (n + 1) / 2;
    int sum = 0;
    int l = 1;
    int chep = 0;

    if(n % 2 == 1)
    {
        for(int i = 0; i < n; i++)
        {
            if(sum >= SUM/2)
                chep = 1;

            if(l == 1)
            {
                ans[i + chep] = a[i+chep].second;
                l = 0;
                sum += (a[i+chep].first);
            }
            else
            {
                l = 1;
                sum += (a[n - i + chep].first);
                ans[i + chep] = a[n - i + chep].second;
            }

            if(ans[i] == -1)ans[i] = 1;
        }
        return ans;
    }
    else
    {
        for(int i = 0; i < n; i++)
        {
            if(l == 1)
            {
                ans[i + chep] = a[i+chep].second;
                l = 0;
                sum += (a[i+chep].first);
            }
            else
            {
                l = 1;
                sum += (a[n - i + chep].first);
                ans[i + chep] = a[n - i + chep].second;
            }
        }
        return ans;
    }

}



