#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 };
    if ((int)A.size() == 2) {
        if (A[0] > A[1]) return { 0, 1 };
        return { 1, 0 };
    }
    if ((int)A.size() == 3) {
        if (A[0] >= max(A[1], A[2])) return { 0, 1, 2 };
        if (A[1] >= max(A[0], A[2])) return { 1, 0, 2 };
        return { 2, 0, 1 };
    }
    for (int i = 0; i < (int)A.size(); i++) {
        nxt[i] = -1;
        prv[i] = -1;
    }
    int s, f, m1, m2;
    vector<pair<int, int>> esim;
    for (int i = 0; i < 4; i++) {
        esim.push_back({ A[i], i });
    }
    sort(esim.begin(), esim.end());
    s = esim[1].second;
    m1 = esim[3].second;
    m2 = esim[0].second;
    f = esim[2].second;
    nxt[s] = m1;
    nxt[m1] = m2;
    nxt[m2] = f;
    prv[m1] = s;
    prv[m2] = m1;
    prv[f] = m2;
    long long s1 = A[s] + A[m1];
    long long s2 = A[f] + A[m2];
    for (int i = 5; 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 + A[m] + A[p] - A[m1];
            s = new_s;
            f = new_f;
            m1 = new_m1;
            m2 = new_m2;
            s1 = new_s1;
            s2 = new_s2;
        }
    }
    int t = 1000;
    vector<int> ans;
    ans.push_back(s);
    while (nxt[s] != -1 && t--) {
        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() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    for (int n = 8; n <= 8; 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;
            }
        }
    }
}
*/