#include "souvenirs.h"
#include <utility>
#include <vector>
#include <stack>
using pvi = std::pair<std::vector<int>, long long>;
using ll = long long;
std::vector<ll> fin;
std::vector<ll> counts;
void add(pvi list){
for(auto val: list.first)
++counts[val];
}
void buy_souvenirs(int N, long long P0) {
fin=std::vector<ll>(N, -1);
counts.resize(N);
std::stack<pvi> st;
st.push(transaction(P0-1));
st.top().second=P0-1-st.top().second;
add(st.top());
while(!st.empty()){
pvi& cur=st.top();
while(cur.first.size()>1){
if(fin[(cur.first)[cur.first.size()-1]]!=-1){
cur.second-=fin[cur.first[cur.first.size()-1]];
cur.first.pop_back();
}
else break;
}
if(cur.first.size()==1){
ll ind=(cur.first)[0];
fin[ind]=cur.second;
if(ind<N-1&&fin[ind+1]==-1){
st.push(transaction(fin[ind]-1));
st.top().second=fin[ind]-1-st.top().second;
add(st.top());
}
else
st.pop();
}
else{
ll next_cost=cur.second/(cur.first.size());
st.push(transaction(next_cost));
st.top().second=next_cost-st.top().second;
add(st.top());
}
}
for(int i=0; i < N; ++i){
while(counts[i]<i)
transaction(fin[i]);
}
return;
}
