#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);
P[0] = P0;
vector<long long> bought(N, 0);
auto do_call = [&](long long M) -> int {
auto [L, R] = transaction(M);
for (int t: L) bought[t]++;
return L.empty() ? N : L[0];
};
// GLOBAL valid lower bound: all calls must have M >= LB.
long long LB = P0 - 1; // guaranteed >= P[N-1]
// Make one call to record purchases and confirm LB is valid (optional but helpful).
// (Uncomment if you want at least one data point)
// do_call(LB);
// Tight per-index search windows; they must always include LB.
vector<long long> lo(N, -1), hi(N, P0 - 1);
for (int k = N - 1; k >= 1; --k) {
// Set the best-known window using neighbors we may have already found
long long L = max(LB, (k + 1 < N && P[k + 1] != -1) ? P[k + 1] + 1 : LB);
long long R = (k - 1 >= 1 && P[k - 1] != -1) ? min(hi[k], P[k - 1] - 1) : hi[k];
// Safe binary search: mid is always in [LB, R].
while (L < R) {
long long mid = L + ((R - L) >> 1);
// Ensure mid is within [LB, P0-1]
if (mid < LB) mid = LB;
int first = do_call(mid); // ALWAYS valid: mid >= LB
if (first <= k) {
R = mid;
} else {
L = mid + 1;
}
// Any M we just called is valid; if it’s smaller than LB, promote LB down.
if (mid < LB) LB = mid; // (redundant due to guard)
if (L < LB) L = LB; // keep L >= LB
}
P[k] = L; // minimal M with first <= k is exactly P[k]
// After discovering a new smaller valid M (=P[k]), we can lower LB to it.
if (P[k] < LB) LB = P[k];
}
// Phase B: top-up to exact targets T[i] = i (and T[0] = 0), without buying extras
for (int i = 1; i < N; ++i) {
long long need = i - bought[i];
while (need-- > 0) {
// Buy exactly one i: choose M so higher types can't be bought, and
// remainder after buying i is < P[i+1] (or no i+1).
long long headRoom = (i - 1 >= 1 ? P[i - 1] - 1 : P0 - 1);
long long tailCap = (i + 1 < N ? P[i + 1] - 1 : (P0 - 1 - P[i]));
long long M = P[i] + max(0LL, min(tailCap, headRoom - P[i]));
if (M < LB) M = LB; // keep it valid
auto [Lvec, R] = transaction(M);
for (int t: Lvec) bought[t]++;
}
}
}
