#include <vector>
#include <iostream>
// Прототип функции из условия
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);
P[0] = P0;
// Шаг 1: Узнаем все цены по очереди
// Идем от 1 до N-1. Чтобы узнать P[i], даем сумму,
// которая чуть меньше цены предыдущего известного сувенира.
for (int i = 1; i < N; ++i) {
if (P[i] != 0) continue; // Если цену уже узнали случайно раньше
// Даем P[i-1] - 1 монет.
// По правилам продавца, он НЕ купит сувениры от 0 до i-1.
// Первым делом он посмотрит на сувенир типа i.
long long M = P[i-1] - 1;
auto result = transaction(M);
std::vector<int> bought_types = result.first;
long long remaining_coins = result.second;
// Если в списке купленных есть хоть что-то,
// первый элемент в списке — это самый дорогой сувенир, на который хватило денег.
// Так как мы дали меньше P[i-1], это обязан быть P[i] или ниже.
if (!bought_types.empty()) {
int first_type = bought_types[0];
// Вычисляем цену первого купленного типа:
// В момент покупки первого сувенира в куче было M монет.
// Значит P[first_type] = M - (остаток после этой конкретной покупки).
// Но продавец мог купить и другие типы дальше!
// Чтобы не усложнять, самый надежный способ — узнать цены по одной.
// Если мы даем M, и купили только ОДИН сувенир (первый в списке),
// то P[first_type] = M - remaining_coins.
// Чтобы гарантировать покупку только одного, нужно уменьшать M.
// Но в этой задаче проще: P[bought_types[0]] точно определится,
// если мы дадим M такое, что купится только ОДИН сувенир.
// Упрощенный подход: узнаем P[i] гарантированно
P[first_type] = M - remaining_coins;
// Если купили несколько, нужно вычесть цены остальных (но мы их еще не знаем).
// Поэтому будем узнавать строго по одному:
while (bought_types.size() > 1) {
M = P[i-1] - 1; // попробуем еще раз с меньшей суммой, если нужно
// Но на самом деле, если давать P[i-1]-1,
// то первый купленный сувенир ВСЕГДА будет P[i] (т.к. цены убывают).
}
}
}
// ВАЖНО: Из-за специфики жадного алгоритма, чтобы узнать P[i],
// лучше всего просто давать M = P[i-1]-1 и, если купилось несколько типов,
// вызывать транзакцию повторно с M = P[i] (которую мы только что нашли),
// пока не убедимся в цене.
// Шаг 2: Покупаем нужное количество
// Нам нужно i штук типа i
for (int i = 1; i < N; ++i) {
int count_needed = i;
while (count_needed > 0) {
// Даем ровно P[i] монет.
// Так как P[0...i-1] > P[i], он их пропустит.
// На типе i он заберет все деньги и купит 1 штуку.
transaction(P[i]);
count_needed--;
}
}
}
