#include "partition.h"
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <unordered_map>
#include <utility>
using namespace std;

int getDiff(std::vector<int> ans) {
	long long total = ans.size() * (1 + ans.size()) / 2;
	long long sum = 0;
	int cnt = 0;
	for (auto a : ans) {
		cnt++;
		sum += a + 1;
		if (sum >= total / 2 + total % 2) {
			break;
		}
	}
	auto abs = [](int x) {
		if (x < 0)
			return -x;
		return x;
	};
	return abs(cnt - (ans.size() - cnt));
}

std::vector<int> solve(std::vector<int> A) {
	vector<int> ans;
	if (A.size() == 1) {
		return {0};
	}
	int pairCount = A.size() / 2;
	if (A.size() % 2 == 0) {
		for (int i = 0; i < A.size() / 2; i++) {
			ans.push_back(A.size() - i - 1);
			ans.push_back(i);
		}
	} else {
		for (int i = 0; i < A.size() / 2; i++) {
			ans.push_back(A.size() - i - 1);
			if (pairCount % 2 == 1 && i == pairCount / 2) {
				ans.push_back(A.size() / 2);
			}
			ans.push_back(i);
			if (pairCount % 2 == 0 && i == pairCount / 2 - 1) {
				ans.push_back(A.size() / 2);
			}
		}
	}
	return ans;
}
