#ifndef LOCAL
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC diagnostic ignored "-Wpedantic"
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(52);
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename V>
using table = gp_hash_table<T, V>;
using i128 = __int128;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const ll INF = 2e18;
const int inf = 2e9;
const int maxn = 1e5;
const int MOD = 988244353;
const ld pi = acos(-1);
const int P = 5167;
const int L = 26;
const ld EPS = 1e-7;
template<typename T, typename V>
void fill(T &container, V value) {
for (auto &c: container)
c = value;
}
ll calculate_acute_value(int val1, int val2) {
ll diff_abs = abs(static_cast<ll>(val1) - val2);
ll val = min(diff_abs, 50000LL - diff_abs);
return val;
}
void rotate(vector<int> t, int x);
void energy(int n, vector<int> v_initial) {
vector<int> v = v_initial;
ll total_rods_selected_count = 0;
if (n <= 2000) {
for (int pass = 0; pass < 3; ++pass) {
bool changed_in_pass = false;
if (total_rods_selected_count >= 2000000) break;
for (int i = 0; i < n; ++i) {
if (total_rods_selected_count >= 2000000) break;
int current_vi = v[i];
int target_T;
ll dist_to_0 = calculate_acute_value(current_vi, 0);
ll dist_to_25000 = calculate_acute_value(current_vi, 25000);
if (dist_to_0 <= dist_to_25000) {
target_T = 0;
} else {
target_T = 25000;
}
if (current_vi == target_T) {
continue;
}
int rotation_x = (target_T - current_vi + 50000) % 50000;
ll delta_E = 0;
for (int j = 0; j < n; ++j) {
if (i == j) continue;
ll old_acute_ij = calculate_acute_value(current_vi, v[j]);
ll new_acute_ij = calculate_acute_value(target_T, v[j]);
delta_E += (new_acute_ij - old_acute_ij);
}
if (delta_E >= 0) {
if (total_rods_selected_count + 1 <= 2000000) {
rotate({i}, rotation_x);
v[i] = target_T;
total_rods_selected_count++;
changed_in_pass = true;
} else {
return;
}
}
}
if (!changed_in_pass) {
break;
}
}
} else {
vector<pair<ll, int>> preferences(n);
for (int i = 0; i < n; ++i) {
ll dist_to_0 = calculate_acute_value(v[i], 0);
ll dist_to_25000 = calculate_acute_value(v[i], 25000);
preferences[i] = {dist_to_0 - dist_to_25000, i};
}
sort(preferences.begin(), preferences.end());
vector<int> targets(n);
int count_for_pole_0 = n / 2;
for (int k = 0; k < count_for_pole_0; ++k) {
targets[preferences[k].second] = 0;
}
for (int k = count_for_pole_0; k < n; ++k) {
targets[preferences[k].second] = 25000;
}
map<int, vector<int>> rotations_to_perform;
for (int i = 0; i < n; ++i) {
if (v[i] == targets[i]) continue;
int rotation_x = (targets[i] - v[i] + 50000) % 50000;
if (rotation_x == 0) continue;
rotations_to_perform[rotation_x].push_back(i);
}
for (auto const& pair_rot_indices : rotations_to_perform) {
int rot_val = pair_rot_indices.first;
const vector<int>& indices = pair_rot_indices.second;
if (indices.empty()) continue;
if (total_rods_selected_count + indices.size() <= 2000000) {
rotate(indices, rot_val);
total_rods_selected_count += indices.size();
for (int rod_idx : indices) {
v[rod_idx] = targets[rod_idx];
}
} else {
for (int rod_idx : indices) {
if (total_rods_selected_count + 1 <= 2000000) {
rotate({rod_idx}, rot_val);
v[rod_idx] = targets[rod_idx];
total_rods_selected_count++;
} else {
return;
}
}
}
if (total_rods_selected_count >= 2000000) return;
}
}
}
