#include <bits/stdc++.h>
using namespace std;
int n;
long long pref[2000005];
long long suff[2000005];
vector <int> print(int x, int y, vector <pair <int, int> >& v)
{
    vector <int> ans;
    for(int i = 1; i <= x; i++)
    {
        ans.push_back(v[i].second);
    }
    for(int i = n; i >= y; i--)
    {
        ans.push_back(v[i].second);
    }
    for(int i = x+1; i < y; i++)
    {
        ans.push_back(v[i].second);
    }
    return ans;
}
void merge_sort(vector < pair <int, int> > &v)
{
    if(v.size() == 1)return;
    if(v.size() == 2)
    {
        if(v[0].first < v[1].first)return;
        else swap(v[0], v[1]);
    }
    int mid = v.size()/2;
    vector <pair <int, int> > v1, v2;
    for(int i = 0; i <= v.size(); i++)
    {
        if(v[i].first <= v[mid].first)v1.push_back(v[i]);
        else v2.push_back(v[i]);
    }
    merge_sort(v1);
    merge_sort(v2);
    int pos1 = 0, pos2 = 0;
    v.clear();
    while(pos1 < v1.size() && pos2 < v2.size())
    {
            if(v1[pos1].first < v2[pos2].first)
            {
                v.push_back(v1[pos1]);
                pos1++;
            }
            else
            {
                v.push_back(v2[pos2]);
                pos2++;
            }

    }
    while(pos1 < v1.size())
    {
        v.push_back(v1[pos1]);
        pos1++;
    }
    while(pos2 < v2.size())
    {
        v.push_back(v2[pos2]);
        pos2++;
    }
}
std::vector<int> solve(std::vector<int> A)
{
    vector <pair<int, int> > v;
    n = A.size();
    v.push_back({0, 0});
    for(int i = 0; i < n; i++)
    {
        v.push_back({A[i], i});
    }
    ///merge_sort(v);
    if(n == 1)return {0};
    if(n == 2)return {v[2].second, v[1].second};
    pref[0] = 0;
    for(int i = 1; i <= n; i++)
        pref[i] = pref[i-1] + v[i].first;
    suff[n+1] = 0;
    for(int j = n; j > 0; j--)
        suff[j] = suff[j+1] + v[j].first;
    int minc = 1e9, x = 0, y = 0;
    long long s = pref[n]/2 + pref[n]%2;
    int pos = 1;
    for(int i = 0; i <= n; i++)
    {
        if(pref[i] >= s)
        {
            ///cout << pref[i] << endl;
            if(abs(n-2*i) <= minc)
            {
                ///cout << 1 << endl;
                x = i;
                y = n+1;
                minc = abs(n - 2*i);
            }
        }
        else
        {
            while(suff[pos] >= s - pref[i])pos++;
            pos--;
            int cnt = i + (n-pos+1);
            if(minc > abs(n - 2*cnt))
            {
                minc = abs(n-2*cnt);
                x = i;
                y = pos;
            }
        }
    }
    return print(x, y, v);
}
