#include <bits/stdc++.h>
using namespace std;
pair<vector<int>, long long> transaction(long long M);
void buy_souvenirs(int N, long long P0) {
vector<long long> P(N);
P[0] = P0;
long long knownTailSum = 0;
// Recover prices from high indices downward
for (int i = N - 1; i >= 1; --i) {
long long M = P0 - 1 - knownTailSum;
auto res = transaction(M);
long long selectedSum = M - res.second;
long long tailContribution = 0;
bool found = false;
for (int idx : res.first) {
if (idx > i)
tailContribution += P[idx];
if (idx == i)
found = true;
}
if (found) {
P[i] = selectedSum - tailContribution;
} else {
// probe boundary
long long M2 = M - 1;
auto res2 = transaction(M2);
long long sel2 = M2 - res2.second;
long long tail2 = 0;
bool found2 = false;
for (int idx : res2.first) {
if (idx > i) tail2 += P[idx];
if (idx == i) found2 = true;
}
if (found2)
P[i] = sel2 - tail2;
else
P[i] = (M2 - tailContribution) + 1;
}
knownTailSum += P[i];
}
// Purchase required souvenirs
for (int t = 1; t < N; ++t) {
for (int rep = 0; rep < t; ++rep) {
long long M = P[t];
for (int j = N - 1; j > t; --j)
if (M + P[j] < P0)
M += P[j];
transaction(M);
}
}
}
