#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include<algorithm>
using namespace std;
#define SUBMIT 1
const int m = 100000;
void energy(int n, vector<int> v);
void rotate(vector<int> t, int x);
void send(int i, int cp, int np) {
np %= m, cp %= m;
int d = (np + m - cp) % m;
rotate({ i }, d);
}
void energy(int n, vector<int> v) {
if (n == 2)
send(1, v[1], v[0] + m / 4);
else {
vector<int> p;
int deg = m / 2, rod = 0, pos = 0;
for (int rod = 0; rod < n; ++rod) {
int lft = n - rod;
int cur = deg / lft;
pos += cur;
p.push_back(pos);
deg -= cur;
}
sort(p.begin(), p.end());
vector<pair<int, int>> a(n);
for (int i = 0; i < n; ++i)
a[i] = { v[i], i };
sort(a.begin(), a.end());
for (int i = n - 1; i >= 0; --i)
send(a[i].second, a[i].first,
(i >= n / 2)? m / 4: 0);
}
}
//grader
#if SUBMIT == 0
#include <cstdio>
#include <cstdlib>
#include <set>
static int total_cost = 0;
static vector<int> v;
static FILE* file_log;
static void printf_vector(vector<int> vec) {
printf("[");
for (int i = 0; i < (int)vec.size(); i++) {
if (i > 0) printf(", ");
printf("%d", vec[i]);
}
printf("]");
}
static long long calc_energy() {
sort(v.begin(), v.end());
long long ans = 0;
long long cur = 0;
for (auto& x : v) cur += x;
for (int i = 0; i < v.size(); ++i) {
cur -= v[i];
ans += cur - v[i] * ((int)v.size() - i - 1);
}
return ans;
}
static long long last_energy;
int cnt = 1000;
void rotate(vector<int> t, int x) {
--cnt;
int k = (int)t.size();
total_cost += k;
if (total_cost > 2000000) {
printf("Too many rotations\n");
exit(0);
}
set<int> seen;
for (int i = 0; i < k; i++) {
if (t[i] < 0 || t[i] >= (int)v.size()) {
printf("Invalid index\n");
exit(0);
}
if (seen.find(t[i]) != seen.end()) {
printf("t has duplicate element\n");
exit(0);
}
v[t[i]] = (v[t[i]] + x) % 50000;
seen.insert(t[i]);
}
printf("rotate(");
printf_vector(t);
printf(", %d)\n", x);
/// printf("v <- ");
/// printf_vector(v);
///printf("\n");
if (cnt == 0) {
long long cur_energy = calc_energy();
printf("New energy: %lld\n", cur_energy);
printf("\n");
if (cur_energy < last_energy) {
printf("Energy decreased\n");
exit(0);
}
cnt = 10;
last_energy = cur_energy;
}
}
int main() {
int n;
scanf("%d", &n);
v.resize(n);
for (int i = 0; i < n; i++) {
scanf("%d", &v[i]);
}
last_energy = calc_energy();
file_log = fopen("log.txt", "w");
printf("Initial energy: %lld\n\n", last_energy);
energy(n, v);
fclose(file_log);
printf("%lld\n", calc_energy());
return 0;
}
#endif
