#include <bits/stdc++.h>
using namespace std;
// Provided by the grader.
extern pair<vector<int>, long long> transaction(long long M);
static const long long INF = (1LL<<62);
void buy_souvenirs(int N, long long P0) {
vector<long long> P(N);
P[0] = P0;
// Track how many of each type we've already bought (counts all queries).
vector<long long> bought(N, 0);
auto call = [&](long long M)->int {
auto [L, R] = transaction(M);
for (int t: L) bought[t]++; // count all purchases
if (L.empty()) return N; // "none"
return L[0]; // first bought index
};
// Helper: do a safe call that buys at most one item when it hits index k.
auto call_capped = [&](long long M, int k)->int {
// If we know P[k+1], cap M so that after buying k, remainder < P[k+1].
if (k+1 < N && P[k+1] > 0) {
// Ensure M <= P[k] + P[k+1] - 1 when searching "in the zone".
// We'll clamp downwards if needed (P[k] might still be unknown during search;
// in that case we can't cap by it yet and just use M).
if (P[k] > 0) {
long long cap = P[k] + P[k+1] - 1;
if (cap < M) M = cap;
}
}
return call(M);
};
// ----- Phase A: recover all P[k], k = N-1..1 -----
// We keep dynamic search bounds per k: [lo_k, hi_k] such that P[k] in [lo_k, hi_k].
vector<long long> lo(N, 1), hi(N, P0-1);
// Unknowns are P[1..N-1]. We'll find from bottom to top to learn P[k+1] first.
// For k=N-1 initially we don't know hi; it's P[N-2]-1, but we can start with P0-1 safely.
// We will progressively tighten using known neighbors.
for (int k = N-1; k >= 1; --k) {
// If we already know next and prev thresholds, shrink bounds.
if (k+1 < N && P[k+1] > 0) lo[k] = max(lo[k], P[k+1] + 1);
if (k-1 >= 1 && P[k-1] > 0) hi[k] = min(hi[k], P[k-1] - 1);
// Binary search minimal M with f(M) <= k
long long L = lo[k], R = hi[k];
// Guard: ensure L<=R (it will be, but be safe)
if (L < 1) L = 1;
if (R >= P0) R = P0-1;
// We’ll use standard binary search. To reduce extra buys,
// when we detect f(M)==k we try to keep M <= P[k]+P[k+1]-1 once P[k] is known
// (not known on first hits; it's okay).
while (L < R) {
long long mid = L + ((R - L) >> 1);
int first = call(mid); // single call; counts purchases
if (first <= k) {
R = mid;
} else {
L = mid + 1;
}
}
// L=R is the minimal M where first<=k; this equals P[k].
// Do one more call at M=L to also capture the remainder if you want (not necessary).
// But we may have already called it as last 'mid'; if not, call it now.
// We need the value P[k], not the items from the call. To avoid another call,
// just set P[k]=L directly; correctness: by the monotonicity argument, the minimal M is exactly P[k].
P[k] = L;
}
// ----- Phase B: top-up to exact targets with few calls -----
// Target: T[0]=0, T[i]=i for i>=1
for (int i = 1; i < N; ++i) {
long long need = i - bought[i];
while (need > 0) {
// Buy exactly one item of type i.
long long padBelow = (i+1 < N ? P[i+1]-1 : (P0-1 - P[i])); // safe tail pad
if (padBelow < 0) padBelow = 0;
long long M = P[i] + min(padBelow, P0-1 - P[i]); // ensure < P0
// Edge case: if M < P[N-1] (very tiny), bump to P[N-1]
if (M < P[N-1]) M = P[N-1];
auto [L, R] = transaction(M);
for (int t: L) bought[t]++;
// Assert we bought exactly type i
// (In a contest, you can assert and abort; here we just trust the construction.)
need--;
}
}
}
