#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void buy_souvenirs(int N, ll P0) {
vector<ll> P(N, 0ll);
vector<int> freq(N,0ll);
P[0] = P0;
int L = N;
auto rec = [&](ll coins, auto &&self) -> void {
auto [R, ch] = transaction(coins);
for(auto &i : R) {
++freq[i];
}
ll sum = coins - ch;
// for(int j = R.size()-1; j >= 0; --j) {
// int idx = R[j];
// sum -= P[idx];
// }
for(int j = R.size()-1; j >= 0; --j) {
int idx = R[j];
if(idx < L) break;
sum -= P[idx];
R.pop_back();
}
while(R.size() - 1) {
self((sum - ch) / R.size(), self);
// cerr << sum << "->";
for(int j = R.size()-1; j >= 0; --j) {
int idx = R[j];
// cerr << idx;
if(idx < L) break;
sum -= P[idx];
R.pop_back();
}
}
P[R.front()]= sum;
if(L > R.front() + 1ll){
self(sum-1, self);
}
L = R.front();
return;
};
for(int i = 1; i < N; ++i){
while(freq[i] < i) {
++freq[i];
transaction(P[i]);}
}
return;
}
