#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
int n;
vector<int> p, mini, maxi;
bool works(int x, int mid, pair<vector<signed>, int> &res, bool Minimize) {
int valmin=mid, valmax=mid;
bool ok=1;
for (auto y: res.fi) {
if (y<x) {
if (mid+(x-y)>maxi[y]) ok=0;
valmin+=max(mini[y], mid+(x-y));
valmax+=maxi[y];
}
if (y>x) {
if (mid-(y-x)<mini[y]) ok=0;
valmin+=mini[y];
valmax+=min(maxi[y], mid-(y-x));
}
}
return ok && valmin<=res.se && res.se<=valmax;
}
void calc(int x, pair<vector<signed>, int> &res) {
if (sz(res.fi)==1) {
mini[x]=maxi[x]=res.se;
return;
}
{ // calc mini
int l=mini[x], r=maxi[x], ans=mini[x];
while (l<=r) {
int mid=(l+r)/2;
if (works(x, mid, res, 1)) ans=mid, r=mid-1;
else l=mid+1;
}
mini[x]=ans;
}
{ // calc maxi
int l=mini[x], r=maxi[x], ans=maxi[x];
while (l<=r) {
int mid=(l+r)/2;
if (works(x, mid, res, 0)) ans=mid, l=mid+1;
else r=mid-1;
}
maxi[x]=ans;
}
}
vector<pair<vector<signed>, int>> res;
vector<vector<int>> used;
void process(int id) {
for (auto x: res[id].fi) {
calc(x, res[id]);
// cout << mini[x] << ' ' << maxi[x] << endl;
if (mini[x]==maxi[x]) {
// cout << x << endl;
p[x]=mini[x];
for (auto &y: used[x]) {
res[y].se-=p[x];
res[y].fi.erase(find(all(res[y].fi), x));
}
// for (int i=0; i<n; i++) {
// cout << i << ' ' << mini[i] << ' ' << maxi[i] << ' ' << p[i] << endl;
// }
for (int i=0; i<x; i++) if (p[i]==-1) cmax(mini[i], p[x]+(x-i));
for (int i=x+1; i<n; i++) if (p[i]==-1) cmin(maxi[i], p[x]-(i-x));
for (auto &y: used[x]) process(y);
used[x].clear();
return;
}
}
}
void buy_souvenirs(signed N, long long P0) {
n=N; p.resize(n, -1); p[0]=P0;
vector<int> cnt(n, 0);
mini.resize(n); maxi.resize(n); mini[0]=maxi[0]=P0;
for (int i=1; i<n; i++) mini[i]=n-i, maxi[i]=P0-i;
used.resize(n);
while (1) {
int best=-1, bestv=-1;
for (int i=1; i<n; i++) if (p[i]==-1) {
if (maxi[i]<bestv || bestv==-1) bestv=maxi[i], best=i;
}
if (best==-1) break;
int i=best;
assert(cnt[i]<=i);
// cout << i << ' ' << mini[i] << ' ' << maxi[i] << endl;
auto r=transaction(maxi[i]);
res.pb({{}, 0}); res.back().se=maxi[i]-r.se;
for (auto x: r.fi) {
cnt[x]++;
assert(cnt[x]<=x);
if (p[x]!=-1) {
res.back().se-=p[x];
} else {
res.back().fi.pb(x);
used[x].pb(sz(res)-1);
}
}
if (r.fi.back()+1<n) cmax(mini.back(), r.se+1);
for (int j=n-2; j>r.fi.back(); j--) cmax(mini[j], mini[j+1]+1);
process(sz(res)-1);
}
for (int i=1; i<n; i++) {
assert(cnt[i]<=i);
if (cnt[i]==i) continue;
// while (mini[i]<maxi[i]) {
// cout << i << ' ' << mini[i] << ' ' << maxi[i] << endl;
// if (cnt[i]>i) assert(0);
// auto r=transaction(maxi[i]);
// res.pb({{}, 0}); res.back().se=maxi[i]-r.se;
// for (auto x: r.fi) {
// cnt[x]++;
// if (p[x]!=-1) {
// res.back().se-=p[x];
// } else {
// res.back().fi.pb(x);
// used[x].pb(sz(res)-1);
// }
// }
// process(sz(res)-1);
// }
while (cnt[i]<i) cnt[i]++, transaction(p[i]);
}
return;
}
