#include "partition.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
#include <queue>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define int long long

using ll = long long;
using pii = pair<int, int>;

constexpr int MAXN = 2000000;
constexpr int BULAN = 2000;

int n;
priority_queue<pii> pq;

struct Dsu
{
	struct Data
	{
		int p;
		int lazy;
	};
	Data v[MAXN+2];
	void init()
	{
		for (int i = 0; i < n; i++) {
			v[i].p = -1;
			v[i].lazy = 0;
		}
	}
	int root(int node)
	{
		if (v[node].p < 0) return node;
		int r = root(v[node].p);
		if (v[node].p != r) {
			v[node].lazy ^= v[v[node].p].lazy;
			v[node].p = r;
		}
		return r;
	}
	int getVal(int node)
	{
		int r = root(node);
		if (node == r) return v[node].lazy;
		return v[node].lazy ^ v[r].lazy;
	}
	void merge(int a, int b)
	{
		v[a].p += v[b].p;
		v[b].p = a;
		v[b].lazy ^= (v[a].lazy ^ 1);
	}
} dsu;

vector<signed> solve(vector<signed> A) {
    n = A.size();
	dsu.init();
	for (int i = 0; i < n; i++) {
		pq.push({A[i], i});
	}
	while (pq.size() > 1) {
		pii a = pq.top();
		pq.pop();
		pii b = pq.top();
		pq.pop();
		if (a.first < b.first) {
			swap(a, b);
		}
		dsu.merge(a.second, b.second);
		pq.push({a.first-b.first, a.second});
	}
	while (!pq.empty()) {
		pq.pop();
	}
	vector<signed> ansvec;
	for (int i = 0; i  < n; i++) {
		if (dsu.getVal(i) == 0) {
			ansvec.push_back(i);
		}
	}
	for (int i = 0; i < n; i++) {
		if (dsu.getVal(i) == 1) {
			ansvec.push_back(i);
		}
	}
	return ansvec;
}
