#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using lli = long long;
const lli inf_64 = 0x3f3f3f3f3f3f3f3f;
void buy_souvenirs(int N, lli P0) {
vector <lli> cost(N, -1);
vector <int> times(N);
cost[0] = P0;
auto Trim = [&] (vector <int>& item_idx, lli& total) -> void {
vector <int> new_list;
for (int p : item_idx) {
if (cost[p] != -1) {
total -= cost[p];
} else {
new_list.push_back(p);
}
}
item_idx = move(new_list);
};
auto Min_Sum = [&] (lli r, vector <int> item_idx) -> lli {
lli sum = r;
int p = (int) item_idx.size() - 2;
for (int i = item_idx.back() - 1; i >= item_idx[0]; --i) {
r += 1;
if (cost[i] != -1) r = max(r, cost[i]);
if (item_idx[p] == i) {
sum += r; --p;
}
}
return sum;
};
auto Solve = [&] (auto self, vector <int> item_idx, lli total) -> void {
// cerr << "DEBUG" << '\n';
// for (int p : item_idx) cerr << p << " ";
// cerr << "\n" << total << "\n";
for (int p : item_idx) {
times[p] += 1;
}
Trim(item_idx, total);
while ((int) item_idx.size() > 1) {
lli v_l = 0, v_r = inf_64;
for (int i = 0; i < item_idx.back(); ++i) {
v_r -= 1;
if (cost[i] != -1) v_r = min(v_r, cost[i]);
}
v_r -= 1;
for (int i = N - 1; i > item_idx.back(); --i) {
v_l += 1;
if (cost[i] != -1) v_l = max(v_l, cost[i]);
}
v_l += 1;
while (v_l <= v_r) {
lli v_mid = (v_l + v_r) >> 1;
if (Min_Sum(v_mid, item_idx) <= total) {
v_l = v_mid + 1;
} else {
v_r = v_mid - 1;
}
}
vector <int> new_idx;
lli new_total;
tie(new_idx, new_total) = transaction(v_r);
new_total = v_r - new_total;
self(self, new_idx, new_total);
Trim(item_idx, total);
}
if (not item_idx.empty()) {
cost[item_idx[0]] = total;
}
};
for (int i = 1; i < N; ++i) {
if (cost[i] != -1) continue;
// cerr << "ASK FOR: " << i << " " << cost[i - 1] - 1 << '\n';
vector <int> item_idx;
lli value;
tie(item_idx, value) = transaction(cost[i - 1] - 1);
value = cost[i - 1] - 1 - value;
Solve(Solve, item_idx, value);
}
// cerr << "DEBUG\n";
// for (lli c : cost) cerr << c << " ";
// cerr << '\n';
for (int i = 0; i < N; ++i) {
while (times[i] < i) {
++times[i];
transaction(cost[i]);
}
}
}
