#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 };
    for (int i = 0; i < (int)A.size(); i++) {
        nxt[i] = -1;
        prv[i] = -1;
    }
    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;
    int q = s;
    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 + A[p] + A[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 {
            int q = prv[m1];
            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[q] = -1;
            prv[m2] = -1;
            int new_s = m2;
            int new_f = q;
            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;
        }
        /*
        cout << "start finish: " <<  s << " " << f << "\n";
        int q = s;
        vector<int> ans = { q };
        while (q != f) {
            q = nxt[q];
            ans.push_back(q);
        }
        cout << "! ";
        for (auto it : ans) {
            cout << it << " ";
        }
        cout << "\n";
        for (int i = 0; i < (int)ans.size() - 1; i++) {
            if (nxt[ans[i]] != ans[i + 1]) {
                cout << "fatal error\n";
                return {};
            }
        }
        if (nxt[ans.back()] != -1) {
            cout << "fatal error\n";
            return {};
        }
        if (prv[0] != -1) {
            cout << "fatal error\n";
            return {};
        }
        for (int i = 1; i < (int)ans.size(); i++) {
            if (prv[ans[i]] != ans[i - 1]) {
                cout << "fatal error\n";
                return {};
            }
        }
        cout << s1 << " " << s2 << "\n";*/
    }
    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> v = {4, 2, 2, 5, 4, 1};
    for (auto it : solve(v)) {
        cout << it << " ";
    }
    cout << "\n";
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    for (int n = 4; n <= 10; n++) {
        int t = 1000;
        while (t--) {
            vector<int> v(n);
            int s = 0;
            for (auto &it : v) {
                it = rng() % 10 + 1;
                s += it;
            }
            vector<int> ord = solve(v);
            int cur = 0;
            int ind = 0;
            for (int i = 0; i < (int)ord.size(); i++) {
                cur += v[ord[i]];
                if (2 * cur >= s) {
                    ind = i;
                    break;
                }
            }
            if (ind != (n - 1) / 2 && ind != (n - 2) / 2) {
                cout << "! ";
                cout << n << "\n";
                for (auto it : v) {
                    cout << it << " ";
                }
                cout << "\n";
                for (auto it : ord) {
                    cout << it << " ";
                }
                cout << "\n";
                return 0;
            }
        }
    }
}
*/