#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;

bool used[N];

vector<int> solve(vector<int> a) {
	int n = a.size(), mx = 0, indmx = -1;
	ll s = 0;
	for (int i = 0; i < n; ++i) {
		s += a[i];
		if (a[i] > mx) {
			mx = a[i];
			indmx = i;
		}
	}
	swap(a[indmx], a[n - 1]);
	ll sl = 0;
	for (int i = 0; i + 2 < n; ++i) {
		sl += min(a[i], a[i + 1]);
	}
	vector<int> ans(n);
	int pt = 0;
	fill(used, used + n, 0);
	for (int i = 0; i + 2 < n; ++i) {
		if ((sl + mx) * 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;
			}
		}
		++i;
	}
	int pos = pt;
	ans[pt++] = indmx;
	used[indmx] = 1;
	for (int i = 0; i + 1 < n; ++i) {
		if (!used[i]) ans[pt++] = i;
	}
	for (int i = 0; i < n; ++i) {
		if (i != pos && ans[i] == indmx) ans[i] = n - 1;
	}
	return ans;
}

void solve() {
	vector<int> ans = solve({ 5, 6, 6, 3, 1, 1, 4, 4, 3 });
	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;
//}