#include "souvenirs.h"
#include <utility>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
using ll = long long;
#define endl '\n'
#define f first
#define s second
void buy_souvenirs(int N, long long P0) {
vector<ll> minP(N);
vector<ll> maxP(N);
vector<int> cnt(N);
vector<pair<vector<int>,ll>> query;
int cur = N-1;
minP[0] = P0;
maxP[0] = P0;
for(int i{1};i < N;i++){
maxP[i] = maxP[i-1]-1;
minP[i] = N-i;
}
while(cur != 0){
// cout << "Max : ";
// for(auto k:maxP) cout << k << " ";
// cout << endl;
// cout << "Min : ";
// for(auto k:minP) cout << k << " ";
// cout << endl;
pair<vector<int>,ll> ret = transaction(maxP[cur]);
ll use = maxP[cur]-ret.s;
query.push_back({ret.f,use});
for(auto k:ret.f){
cnt[k]++;
}
for(auto [a,b]:query){
ll over = 0;
int si = a.size();
for(auto k:a){
over += N-k;
}
int last = N;
for(int i{si-1};i >= 0;i--){
int k = a[i];
over -= (i+1)*(last-k);
if(maxP[k] != minP[k]) maxP[k] = min(maxP[k],(b-over)/(i+1));
if(i == si-1){
minP[a[0]] = max(minP[a[0]],(b-over)/(i+1));
}
b -= minP[k];
last = k;
}
for(int i{1};i < N;i++){
maxP[i] = min(maxP[i],maxP[i-1]-1);
}
for(int i{N-2};i >= 1;i--){
minP[i] = max(minP[i],minP[i+1]+1);
}
}
cur = 0;
for(int i{1};i < N;i++){
//if(cnt[i] > i) cout << "::: " << i << " ::::" << endl;
if(minP[i] != maxP[i] && cnt[i] != i) cur = max(cur,i);
}
}
// cout << "Max : ";
// for(auto k:maxP) cout << k << " ";
// cout << endl;
for(int i{};i < N;i++){
while(cnt[i] < i){
transaction(maxP[i]);
cnt[i]++;
}
}
return;
}
