#ifndef rtgsp
#include "souvenirs.h"
#endif // rtgsp
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 2e5 + 2;
int n, q[maxn];
ll p[maxn], tot, cnt;
pair<vector<int>, ll> v, t[maxn];
#ifdef rtgsp
ll pp[maxn];
pair<vector<int>, ll> transaction (ll M)
{
vector<int> s;
s.clear();
for (int i = 0; i < n; i++)
{
if (M >= pp[i])
{
M -= pp[i];
s.push_back(i);
}
}
return make_pair(s, M);
}
#endif // rtgsp
void buy_souvenirs(int N, ll P0)
{
n = N;
tot = P0; cnt = 1;
for (int i = 1; i < n; i++) t[i] = {{}, 0};
while (true)
{
assert(tot > 0);
if (cnt == 1)
{
v = transaction(tot - 1);
tot = tot - 1 - v.second;
cnt = v.first.size();
t[v.first[0]] = {v.first, tot};
for (int i : v.first) q[i]++;
}
else
{
v = transaction(tot/cnt);
tot = tot/cnt - v.second;
cnt = v.first.size();
t[v.first[0]] = {v.first, tot};
for (int i : v.first) q[i]++;
}
if (v.first[0] == n - 1) break;
}
for (int i = n - 1; i > 0; i--)
{
if (t[i].second == 0)
{
for (int j = i - 1; j > 0; j--)
{
if (t[j].second == 0) continue;
tot = t[j].second; cnt = t[j].first.size();
for (int k : t[j].first)
{
if (k > i)
{
tot -= p[k];
cnt--;
}
}
break;
}
while (true)
{
if (cnt == 1)
{
v = transaction(tot - 1);
tot = tot - 1 - v.second;
cnt = v.first.size();
t[v.first[0]] = {v.first, tot};
for (int j : v.first) q[j]++;
}
else
{
v = transaction(tot/cnt);
tot = tot/cnt - v.second;
cnt = v.first.size();
t[v.first[0]] = {v.first, tot};
for (int j : v.first) q[j]++;
}
for (int j : v.first)
{
if (j > i)
{
tot -= p[j];
cnt--;
}
}
if (v.first[0] == i) break;
}
}
for (int j : t[i].first)
p[i] -= p[j];
p[i] += t[i].second;
}
for (int i = 1; i < n; i++)
{
while (q[i] < i)
{
v = transaction(p[i]);
assert(v.first.size() == 1);
for (int j : v.first) q[j]++;
}
}
}
#ifdef rtgsp
int main()
{
freopen(task".in", "r", stdin);
//freopen(task".OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
vector<ll> P;
P.clear();
cin >> N;
for (int i = 0; i < N; i++)
{
ll x;
cin >> x;
pp[i] = x;
P.push_back(x);
}
buy_souvenirs(N, P[0]);
}
#endif // rtgsp
