#include "partition.h"
#pragma GCC optimize("unroll-loops", "Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define pb push_back
vector<int> solve(vector<int> a) {
    int n = a.size();
    vector <pair <int, int> > b(n);
    ll sum = 1;
    for (int i = 0; i < n; i++) {
        b[i] = {a[i], i};
        sum += a[i];
    }
    sum /= 2;
    for (int i = 0; i < n; i++) {
        if (a[i] < a[i - 1]) {
            swap(a[i], a[i - 1]);
            swap(b[i], b[i - 1]);
        }
    }
    vector <int> ans(n);
    ll s = 0, s2 = 0;
    for (int i = 0; i < n; i++) {
        if (i & 1) s += b[i].first;
        else s2 += b[i].first;
    }
    if (s > s2) {
        int id = 0;
        for (int i = 1; i < n; i += 2) {
            ans[id] = b[i].second;
            id++;
        }
        for (int i = 0; i < n; i += 2) {
            ans[id] = b[i].second;
            id++;
        }
    } else {
        int id = 0;
        for (int i = 0; i < n; i += 2) {
            ans[id] = b[i].second;
            id++;
        }
        for (int i = 1; i < n; i += 2) {
            ans[id] = b[i].second;
            id++;
        }
    }
    return ans;
}

