#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
void buy_souvenirs(int N, long long P0) {
vector<long long> P(N);
P[0] = P0;
// Step 1: Determine all prices using the structure of subtask 3
for (int i = 0; i < N - 1; ++i) {
auto result = transaction(P[i] - 1);
vector<int> bought = result.first;
long long change = result.second;
if (bought.size() == 1 && bought[0] == i + 1 && change == 0) {
// d_i = 1
P[i + 1] = P[i] - 1;
} else if (bought.size() == 1 && bought[0] == i + 1 && change == 1) {
// d_i = 2
P[i + 1] = P[i] - 2;
} else if (bought.size() == 2 && bought[0] == i + 1 && bought[1] == i + 2 && change == 0) {
// d_i = 2 and P[i+2] = 1
P[i + 1] = P[i] - 2;
if (i + 2 < N) {
P[i + 2] = 1;
}
} else {
// Fallback (should not happen in subtask 3)
if (change == 0) {
P[i + 1] = P[i] - 1;
} else {
P[i + 1] = P[i] - 2;
}
}
}
// Step 2: Compute differences for pairing
vector<int> diff(N - 1);
for (int i = 0; i < N - 1; ++i) {
diff[i] = P[i] - P[i + 1];
}
// Array of needed souvenirs (type 0 is not needed)
vector<int> need(N, 0);
for (int i = 1; i < N; ++i) {
need[i] = i;
}
// Step 3: Pair type i with type N-1 when possible
if (P[N - 1] == 1) {
for (int i = 1; i <= N - 2; ++i) {
while (need[i] > 0 && need[N - 1] > 0 && diff[i - 1] == 2) {
transaction(P[i] + 1);
need[i]--;
need[N - 1]--;
}
}
}
// Step 4: Buy remaining souvenirs individually
for (int i = 1; i < N; ++i) {
while (need[i] > 0) {
transaction(P[i]);
need[i]--;
}
}
}
