#include <vector>
#include <numeric>
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> count(N, 0);
P[0] = P0;
// 1. Узнаем P[N-1] бинарным поиском (диапазон 1...P0-1)
long long low = 1, high = P0 - 1;
while (low <= high) {
long long mid = low + (high - low) / 2;
auto res = transaction(mid);
for (int x : res.first) count[x]++;
if (!res.first.empty() && res.first.back() == N - 1) {
// Если купили N-1, вычисляем его цену
long long s = 0;
for (size_t j = 0; j < res.first.size() - 1; ++j) s += P[res.first[j]];
P[N - 1] = mid - res.second - s;
break;
}
if (res.first.empty() || res.first.back() < N - 1) low = mid + 1;
else high = mid - 1;
}
// 2. Узнаем остальные цены с конца к началу
for (int i = N - 2; i >= 1; --i) {
if (P[i] != 0) continue;
// Даем сумму, которой точно хватит на P[i], но не хватит на P[i-1]
long long M = P[0] - 1;
auto res = transaction(M);
for (int x : res.first) count[x]++;
// В L точно есть i. Вычисляем P[i] = M - R - (сумма цен всех остальных в L)
long long sum_others = 0;
for (int x : res.first) if (x != i) sum_others += P[x];
P[i] = M - res.second - sum_others;
}
// 3. Докупаем до целевых значений
for (int i = 1; i < N; ++i) {
while (count[i] < i) {
auto res = transaction(P[i]);
for (int x : res.first) count[x]++;
}
}
}
