#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
void buy_souvenirs(signed N, long long P0) {
vector<int> numbought(N, 0);
vector<int> P(N, -1);
P[0] = P0;
vector<pair<vector<signed>, int>> vals;
while (true) {
bool done = true;
int crnt = P0, ind = -1;
for (int i = N - 1; i >= 0; i--) {
if (P[i] == -1) {
done = false;
ind = i;
}
if (ind != -1 && P[i] != -1) break;
}
if (done) break;
ind--;
crnt = P[ind];
while (true) {
auto i = transaction(crnt - 1);
i.second = crnt - 1 - i.second;
vector<signed> aaa;
for (int j : i.first) {
numbought[j]++;
if (P[j] == -1) aaa.push_back(j);
else i.second -= P[j];
}
i.first = aaa;
ind = i.first[0];
vals.push_back(i);
for (int j : i.first) {
i.second += j - i.first[0];
}
crnt = (i.second - 1) / i.first.size();
if (i.first.size() == 1) break;
}
auto iter = vals.end();
iter--;
while (iter != vals.begin()) {
vector<signed> aaa;
for (int i : iter->first) {
if (P[i] == -1) aaa.push_back(i);
else iter->second -= P[i];
}
iter->first = aaa;
if (iter->first.size() == 1) {
P[iter->first[0]] = iter->second;
iter = vals.erase(iter);
}
iter--;
}
vector<signed> aaa;
for (int i : iter->first) {
if (P[i] == -1) aaa.push_back(i);
else iter->second -= P[i];
}
iter->first = aaa;
if (iter->first.size() == 1) {
P[iter->first[0]] = iter->second;
vals.erase(iter);
}
}
for (int i = 0; i < N; i++) {
for (int j = numbought[i]; j < i; j++) {
transaction(P[i]);
}
}
return;
}
