#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<random>
#include<ctime>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,sse4,popcnt")

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;

const int N = 2e6 + 2, inf = 1e9 + 100;
const ll llinf = 1e18 + 1000;

char used[N];

vector<int> solve(vector<int> a) {
	int n = a.size();
	ll s = 0;
	for (int i = 0; i < n; ++i) {
		s += a[i];
	}
	ll sl = 0;
	for (int i = 0; i + 1 < n; i += 2) {
		sl += min(a[i], a[i + 1]);
	}
	if (n % 2) sl += a[n - 1];
	vector<int> ans(n);
	int pt = 0;
	fill(used, used + n, 0);
	for (int i = 0; i + 1 < n; i += 2) {
		if (sl * 2 < s) {
			sl += max(a[i], a[i + 1]) - min(a[i], a[i + 1]);
			if (a[i] >= a[i + 1]) {
				used[i] = 1;
				ans[pt++] = i;
			}
			else {
				used[i + 1] = 1;
				ans[pt++] = i + 1;
			}
		}
		else {
			if (a[i] < a[i + 1]) {
				used[i] = 1;
				ans[pt++] = i;
			}
			else {
				used[i + 1] = 1;
				ans[pt++] = i + 1;
			}
		}
	}
	if (n % 2) {
		ans[pt++] = n - 1;
		used[n - 1] = 1;
	}
	int mx = 0;
	for (int i = 1; i < pt; ++i) {
		if (a[ans[i]] > a[ans[mx]]) mx = i;
	}
	swap(ans[mx], ans[pt - 1]);
	for (int i = 0; i < n; ++i) {
		if (!used[i]) ans[pt++] = i;
	}
	return ans;
}

void solve() {
	vector<int> ans = solve({ 5, 5, 1, 3, 3, 1 });
	for (auto i : ans) cout << i << ' ';
}

//signed main() {
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
//	int tt = 1;
//	//cin >> tt;
//	while (tt--) {
//		solve();
//		cout << '\n';
//		cout.flush();
//	}
//	return 0;
//}