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

using namespace std;
using ll = long long;

void coutv(vector<int> v) {
    for (auto u : v) {
        cout << u << endl;
    }
}

vector<int> solve(vector<int> A) {
    ll n = A.size();
    vector<int> ans(n);
    ll S = 0;
    for (auto x : A)
    {
        S += (ll) x;
    }
    ll cur = 0;
    ll cind = 0;
    ll sm = 0;
    vector<bool> used(n, 0);
    while (2 * (sm + (n + 1)) < S)
    {
        ans[cind] = cur;
        used[cur] = 1;
        cind++;
        sm += (cur + 1);
        ans[cind] = n - cur - 1;
        used[n - cur - 1] = 1;
        cind++;
        sm += (n - cur);
        cur++;
    }
    ans[cind] = n - cur - 1;
    used[n - cur - 1] = 1;
    cind++;
    for (ll i = 0; i < n; i++)
    {
        if (!used[i])
        {
            ans[cind] = i;
            cind++;
        }
    }
    //coutv(ans);
    return ans;
}

/*int main()
{
    ll n;
    cin >> n;
    vector<int> A(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    solve(A);
}*/
