#include <bits/stdc++.h>
using namespace std;
// Provided by the grader
extern pair<vector<int>, long long> transaction(long long M);
void buy_souvenirs(int N, long long P0) {
vector<long long> P(N, -1);
vector<long long> cnt(N, 0);
P[0] = P0;
auto buy = [&](long long M, vector<int>& got, long long& change){
auto res = transaction(M);
got = res.first;
change = res.second;
};
// 1) Buy type 1 and deduce P1
{
vector<int> L; long long R;
buy(P0 - 1, L, R); // must buy type 1
P[1] = (P0 - 1) - R;
cnt[1] += 1;
}
// 2) For i=2..N-1, call M = P[i-1]-1 to buy (and learn) type i
for (int i = 2; i < N; ++i) {
if (P[i] != -1) continue; // might already be set by an edge case
vector<int> L; long long R;
long long M = P[i-1] - 1;
buy(M, L, R);
// L is either {i} or {i, i+1} in the only possible double-buy edge case
if (!L.empty() && L[0] == i) {
cnt[i] += 1;
if (L.size() == 2 && L[1] == i+1) { // leftover==1 and P[i+1]==1
P[i] = (M - R) - 1;
P[i+1] = 1;
cnt[i+1] += 1;
} else {
P[i] = (M - R);
}
} else {
// Should not happen under subtask-3 constraints; keep safe fallback
// If we ever land here, we could binary-search with valid Ms,
// but spec guarantees our M is >= P[i] and < P[i-1].
// (Omitted for subtask-3, by design.)
}
}
// 3) Top-up: for each i>=1, reach exactly i items using M = P[i]
for (int i = 1; i < N; ++i) {
while (cnt[i] < i) {
vector<int> L; long long R;
buy(P[i], L, R); // spends exactly P[i], buys exactly type i
cnt[i] += 1;
}
}
}
