#include <bits/stdc++.h>
#include "souvenirs.h"
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
void buy_souvenirs(int n, long long P0) {
vector<ll> b(n,0), mi(n), ma(n), ban(5000,0);
ma[0]=mi[0]=P0;
for(int i=n-1; i>0; i--){
mi[i]=n-i;
ma[i]=P0-i;
}
int pos=n-1;
vector<pair<ll,pair<vector<int>,ll>>> pt;
while(pos!=0){
if(ma[pos]==mi[pos]){
pos--;
continue;
}
pair<vector<int>,ll> res=transaction(ma[pos]);
pt.pb({ma[pos],res});
for(auto au : res.fi) b[au]++;
int e=1;
for(int j=0; j<pt.size(); j++){
int e=0;
if(ban[j]) continue;
auto ar=pt[j].se.fi;
for(int i=0; i<ar.size(); i++){
if(ma[ar[i]]!=mi[ar[i]]) e=1;
}
if(!e) ban[j]=1;
}
for(int k=0; k<pt.size(); k++){
if(ban[k]) continue;
ll c=pt[k].fi, ret=pt[k].se.se;
vector<int> s=pt[k].se.fi;
for(ll i=0; i<s.size(); i++){
if(ma[s[i]]==mi[s[i]]) continue;
ll cmi=ret;
for(ll j=i+1; j<s.size(); j++){
cmi+=mi[s[j]];
}
ll l=mi[s[i]],r=ma[s[i]];
while(l<=r){
ll mid=(l+r)/2;
ll cmi2=0;
for(int j=0; j<i; j++){
cmi2+=max(mi[s[j]],mid+s[i]-s[j]);
}
if(cmi2+cmi+mid<=c) l=mid+1;
if(cmi2+cmi+mid>c) r=mid-1;
}
if(r<ma[s[i]]){
ma[s[i]]=r;
e=1;
for(int j=s[i]+1; j<n; j++){
ma[j]=min(ma[j],ma[j-1]-1);
}
}
ll cma=ret;
for(ll j=0; j<i; j++){
cma+=ma[s[j]];
}
l=mi[s[i]],r=ma[s[i]];
while(l<=r){
ll mid=(l+r)/2;
ll cma2=0;
for(int j=i+1; j<s.size(); j++){
cma2+=min(ma[s[j]],mid+s[i]-s[j]);
}
if(cma2+cma+mid<=c) l=mid+1;
if(cma2+cma+mid>c) r=mid-1;
}
if(r>mi[s[i]]){
mi[s[i]]=r;
e=1;
for(int j=s[i]-1; j>0; j--){
mi[j]=max(mi[j],mi[j+1]+1);
}
}
}
}
}
for(int i=1; i<n; i++){
for(int j=0; j<i-b[i]; j++){
pair<vector<int>,ll> res=transaction(ma[i]);
}
}
return;
}
