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

using namespace std;
const int nmax = 2e6;
struct ura
{
    int ord, val;
}v[nmax + 1];
bool cmp(ura a, ura b)
{
    if(a.val < b.val)
        return true;
    if(a.val > b.val)
        return false;
    return a.ord < b.ord;
}
int vc[nmax + 1];
std::vector<int> solve(std::vector<int> A)
{
    int n = A.size(), i, st = 0, dr = 0, f;
    vector <int> sol(n);
    long long a = 0, b = 0, s = 0;
    f = 0;
    for(i = 1; i < n; i++)
    {
        if(st < dr)
        {
            a += A[i];
            s += A[i];
            vc[i] = 1;
            st++;
            if(a >= (s + 1) / 2)
            {
                b += A[f];
                dr++;
                st--;
                vc[f] = 2;
                f = i;
                vc[i] = 0;
                a-= A[i];
            }
        }
        else
        if(st > dr)
        {
            b += A[i];
            s += A[i];
            vc[i] = 2;
            dr++;
            if(b >= (s + 1) / 2)
            {
                a += A[f];
                st++;
                dr--;
                vc[f] = 1;
                f = i;
                vc[i] = 0;
                b-= A[i];
            }
        }
        else
        {
            if(a < b)
            {
                a += A[i];
                s += A[i];
                vc[i] = 1;
                st++;
                if(a >= (s + 1) / 2)
                {
                    b += A[f];
                    dr++;
                    st--;
                    vc[f] = 2;
                    f = i;
                    vc[i] = 0;
                    a-= A[i];
                }
            }
            else
            {
                b += A[i];
                s += A[i];
                vc[i] = 2;
                dr++;
                if(b >= (s + 1) / 2)
                {
                    a += A[f];
                    st++;
                    dr--;
                    vc[f] = 1;
                    f = i;
                    vc[i] = 0;
                    b-= A[i];
                }
            }
        }
    }
    if(st > dr)
        for(i = 0; i < n - 1; i++)
        {
            if(vc[i] == 1)
                vc[i] = 2;
            else
            if(vc[i] == 2)
                vc[i] = 1;
        }
    for(st = 0, dr = n - 1, i = 0; i < n; i++)
    {
        if(vc[i] == 1)
            sol[st++] = i;
        else
            sol[dr--] = i;
        vc[i] = 0;
    }
    sol[st] = f;
    return sol;
}