//IOI 2025 Day 1 Problem A
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define sz(x) (int) (x).size()
#define vi vector<int>
#define f first
#define s second
#include "souvenirs.h"
/*
namespace {
const int CALLS_CNT_LIMIT = 10'000;
int calls_cnt;
int N;
std::vector<long long> P;
std::vector<int> Q;
void quit(const char* message) {
printf("%s\n", message);
exit(0);
}
} // namespace
std::pair<std::vector<int>, long long> transaction(long long M) {
calls_cnt++;
//cout << M << '\n';
if (calls_cnt > CALLS_CNT_LIMIT)
quit("Too many calls");
if (M >= P[0] || M < P[N - 1])
quit("Invalid argument");
std::vector<int> L;
long long R = M;
for (int i = 0; i < N; i++) {
if (R >= P[i]) {
R -= P[i];
Q[i]++;
L.push_back(i);
}
}
return {L, R};
}*/
void buy_souvenirs(int n, long long int P0){
ll tot[n];
vi calls[n];
ll vals[n];
tot[0] = P0;
calls[0].pb(0);
vals[0] = P0;
//cout << n << " " << P0 << '\n';
//return;
for (int i = n-1; i > 0; i--){
while (sz(calls[i]) == 0){
int idx = i;
for (; idx > 0; idx--) if (sz(calls[idx]) > 0) break;
ll add = 0;
ll mul = 0;
for (int j : calls[idx]){
if (j > i) add += vals[j];
else add += i-j, mul++;
}
ll up = (tot[idx] - add) / mul;
//cout << i << " - " << idx << " " << add << "," << mul << " " << up << '\n';
pair<vi, ll> res = transaction(up);
assert(sz(res.f) > 0);
assert(res.f[0] > idx);
for (int j : res.f) calls[res.f[0]].pb(j);
tot[res.f[0]] = up - res.s;
//for (int j : res.f) cout << j << " ";
//cout << " - " << sz(calls[i]) << "\n";
}
ll temp = tot[i];
for (int j : calls[i]) if (j > i) temp -= vals[j];
vals[i] = temp;
}
int cnts[n];
memset(cnts,0,sizeof(cnts));
for (int i = 0; i < n; i++) for (int j : calls[i]) cnts[j]++;
for (int i = 0; i < n; i++) while (cnts[i] < i) transaction(vals[i]), cnts[i]++;
}
/*
int main() {
assert(1 == scanf("%d", &N));
P.resize(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%lld", &P[i]));
fclose(stdin);
Q.assign(N, 0);
calls_cnt = 0;
buy_souvenirs(N, P[0]);
for (int i = 0; i < N; i++)
printf("%s%d", i ? " " : "", Q[i]);
printf("\n");
fclose(stdout);
return 0;
}
*/
