#include "souvenirs.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define fi first
#define se second
#define tra transaction
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<vector<int>,ll> pvi;
const int MAXN = 2e5+10;
void chmn(auto &a, auto b){ a = min(a, b); }
ll n, c[MAXN], buy[MAXN];
pvi que[MAXN];
void ask(ll las){
// cerr << las <<"ask\n";
auto [aw, sis] = tra(las);
for(auto in : aw) buy[in]++;
vector<int> all;
sis = las-sis;
for(auto in : aw){
if(c[in] != -1) sis -= c[in];
else all.pb(in);
}
if(all.size() == 0) return;
que[all[0]] = pvi(all, sis);
}
void op(){
// cari yg udh tau
bool done = 0;
for(int i=1; i<=n-1; i++){
if(c[i]==-1 && que[i].se!=-1 && que[i].fi.size() == 1){
c[i] = que[i].se;
done = 1;
}
}
// clean
if(done){
for(int i=1; i<=n-1; i++){
if(c[i]!=-1 || que[i].se == -1) continue;
vector<int> baru; ll sis = que[i].se;
for(auto in : que[i].fi){
if(c[in] == -1) baru.pb(in);
else sis -= c[in];
}
que[i] = {baru, sis};
done = 1;
}
}
if(done) return;
// kalo masih ada isinya
for(int i=n-2; i>=1; i--){
if(que[i].se != -1){
int siz = que[i].fi.size();
ll mn = que[i].se/siz;
int ba = que[i].fi.back();
for(int j=ba; j>=0; j--){
if(c[j] == -1) continue;
chmn(mn, c[j]-1);
}
ask(mn);
return;
}
}
// i tau, i+1 ga tau
for(int i=n-2; i>=0; i--){
if(c[i]!=-1 && c[i+1]==-1){
// tanya c[i]-1
ask(c[i]-1);
return;
}
}
}
void buy_souvenirs(int N, long long P0) {
n = N;
c[0] = P0;
for(int i=1; i<=n-1; i++){
c[i] = -1;
que[i] = pvi({}, -1);
}
while(true){
bool done = 0;
for(int i=1; i<=n-1; i++)
done |= (c[i]==-1);
if(!done) break;
op();
// for(int i=1; i<=n-1; i++){
// cerr << c[i] << ' ';
// }
// cerr <<" cost\n";
}
// for(int i=1; i<=n-1; i++){
// cerr << c[i] << ' ';
// }
// cerr <<" cost\n";
for(int i=1; i<=n-1; i++){
while(buy[i] < i){
tra(c[i]); buy[i]++;
}
}
return;
}
