#include <bits/stdc++.h>
std::pair <std::vector <int>, long long> transaction(long long);
void buy_souvenirs(int n, long long p0) {
std::vector <long long> p(n, -1);
p[0] = p0;
std::map <int, std::pair <std::vector <int>, long long>> mp;
mp[0] = { { 0 }, p0 };
std::vector <long long> cnt(n, 0);
auto ask = [&] (long long val) {
auto t = transaction(val);
std::sort(t.first.rbegin(), t.first.rend());
for (int x : t.first) cnt[x]++;
if (t.first.size() == 1) p[t.first[0]] = val - t.second;
if (!mp.count(t.first[0])) mp[t.first[0]] = { t.first, val - t.second };
return t;
};
for (long long avg = p0 - 1; p[n - 1] == -1; ) {
auto t = ask(avg);
avg = (avg - t.second + t.first.size() - 1) / t.first.size() - 1;
}
while (*std::min_element(p.begin(), p.end()) < 0) {
int i = n - 1;
while (p[i] != -1) i--;
while (!mp.count(i)) i--;
bool unkn = false;
for (int x : mp[i].first) if (x != i && p[i] == -1) unkn = true;
if (unkn) {
long long q = mp[i].second;
int tot = 1;
for (int j = 1; j < (int) mp[i].first.size(); j++)
if (p[mp[i].first[j]] != -1)
q -= p[mp[i].first[j]];
else
tot++;
(void) ask((q + tot - 1) / tot - 1);
} else {
long long q = mp[i].second;
for (int j = 1; j < (int) mp[i].first.size(); j++) q -= p[mp[i].first[j]];
p[i] = q;
auto t = ask(q - 1);
}
}
for (int i = 0; i < n; i++) if (cnt[i] < i) ask(p[i]);
}
