#include <vector>
std::pair<std::vector<int>, long long> transaction(long long M);
void buy_souvenirs(int N, long long P0) {
std::vector<long long> P(N, 0);
std::vector<int> current_count(N, 0);
P[0] = P0;
for (int i = 1; i < N; ++i) {
long long low = 1, high = P[i-1] - 1;
long long best_M = high;
// Бинарный поиск минимального M, при котором покупается сувенир типа i
while (low <= high) {
long long mid = low + (high - low) / 2;
auto res = transaction(mid);
for (int x : res.first) current_count[x]++;
bool found_i = false;
for (int x : res.first) if (x == i) found_i = true;
if (found_i) {
// Если купили i, значит P[i] <= mid. Запоминаем цену.
long long sum_others = 0;
for (int x : res.first) if (x != i) sum_others += P[x];
P[i] = mid - res.second - sum_others;
best_M = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
}
for (int i = 1; i < N; ++i) {
while (current_count[i] < i) {
auto res = transaction(P[i]);
for (int x : res.first) current_count[x]++;
}
}
}
