#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void buy_souvenirs(int n, ll p0) {
// std::pair<std::vector<int>, long long> res = transaction(3);
vector<vector<int>> cu(n);
vector<int> amm(n, 0);
int tot = 0;
vector<ll> sus(n, 0);
ll nxt = p0 - 1;
while(!cu.back().size()) {
auto [x, rm] = transaction(nxt);
for(auto y : x) amm[y]++;
tot++;
ll su = nxt - rm;
ll am = x.size();
cu[x[0]] = x;
sus[x[0]] = su;
nxt = (su + am - 1) / am - 1;
}
while(tot < n - 1) {
for(int i = n - 2; i; --i) {
if(!cu[i].size()) break;
while(cu[i].size() > 2) {
sus[i] -= sus[cu[i].back()];
cu[i].pop_back();
}
}
for(int i = n - 2; i; --i) {
if(cu[i].size() && !cu[i + 1].size()) {
while(cu[cu[i].back()].size() == 1) {
sus[i] -= sus[cu[i].back()];
cu[i].pop_back();
}
ll nxt = (sus[i] + (int)cu[i].size() - 1) / (int)cu[i].size() - 1;
auto [x, rm] = transaction(nxt);
for(auto y : x) amm[y]++;
tot++;
cu[x[0]] = x;
ll su = nxt - rm;
sus[x[0]] = su;
break;
}
}
}
for(int i = n - 2; i; --i) {
if(!cu[i].size()) break;
while(cu[i].size() > 2) {
sus[i] -= sus[cu[i].back()];
cu[i].pop_back();
}
}
for(int i = 1; i < n; ++i){
while(amm[i] != i) {
transaction(sus[i]);
amm[i]++;
}
}
}
