#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e6 + 10;
int nxt[N], prv[N];
vector<int> solve(vector<int> A) {
    if ((int)A.size() == 1) return { 0 };
    long long s1 = 0, s2 = 0;
    int s, f, m1, m2;
    if (A[0] > A[1]) {
        s = 0;
        f = 1;
    }
    else {
        s = 1;
        f = 0;
    }
    s1 += A[s];
    s2 += A[f];
    nxt[s] = f;
    prv[s] = -1;
    nxt[f] = -1;
    prv[f] = s;
    m1 = s;
    m2 = f;
    for (int i = 3; i < (int)A.size(); i += 2) {
        int p = i, m = i - 1;
        if (A[p] > A[m]) swap(p, m);
        if (s1 < s2 + p + m) {
            nxt[m1] = m;
            prv[m] = m1;
            nxt[m] = p;
            prv[p] = m;
            nxt[p] = m2;
            prv[m2] = p;
            m1 = m;
            m2 = p;
            s1 += A[m];
            s2 += A[p];
        }
        else {
            prv[m2] = -1;
            nxt[f] = m1;
            prv[m1] = f;
            nxt[m1] = m;
            prv[m] = m1;
            nxt[m] = p;
            prv[p] = m;
            nxt[p] = s;
            prv[s] = p;
            nxt[prv[m1]] = -1;
            int new_s = m2;
            int new_f = prv[m1];
            int new_m1 = m1;
            int new_m2 = m;
            int new_s1 = s2 + A[m1];
            int new_s2 = s1 + m + p - A[m1];
            s = new_s;
            f = new_f;
            m1 = new_m1;
            m2 = new_m2;
            s1 = new_s1;
            s2 = new_s2;
        }
    }
    vector<int> ans;
    ans.push_back(s);
    while (nxt[s] != -1) {
        s = nxt[s];
        ans.push_back(s);
    }
    if ((int)A.size() % 2 == 1) {
        ans.insert(ans.begin() + (int)A.size() / 2, (int)A.size() - 1);
    }
    return ans;
}
/*
int main() {
    vector<int> w = { 5, 6, 6, 3, 1, 1, 4, 4, 3 };
    vector<int> q = solve(w);
    for (auto it : q) {
        cout << it << " ";
    }
    cout << "\n";
}
*/