#include "souvenirs.h"
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
int N;
vector<bool> known;
vector<ll> P;
vector<int> C;
vector<pair<set<int>, ll>> res;
map<ll, pair<vector<int>, ll>> mp;
void know(int i, ll x) {
if (known[i]) return;
// assert(!known[i]);
P[i] = x, known[i] = 1;
for (auto& p : res) {
auto& s = p.first;
auto& x = p.second;
if (s.count(i)) {
s.erase(i);
x -= P[i];
}
if (s.size() == 1) know(*s.begin(), x);
}
}
void cleanup() {
for (auto [s, x] : res) if (s.size() == 1) know(*s.begin(), x);
while (1) {
auto it = res.begin();
while (it != res.end() && !(*it).first.empty()) it++;
if (it == res.end()) break;
res.erase(it);
}
}
pair<set<int>, ll> query(ll M) {
vector<int> v; ll x;
bool f = 0;
if (mp.find(M) == mp.end()) mp[M] = transaction(M), f = 1;
tie(v, x) = mp[M];
x = M - x;
// if (f) {
// cout << M << " :: " << x << " :: ";
// for (int i : v) cout << i << " ";
// cout << "\n";
// }
set<int> s;
for (int i : v) {
if (f) C[i]++;
if (!known[i]) s.insert(i);
else x -= P[i];
}
res.push_back({s, x});
cleanup();
return {s, x};
}
void buy_rest() {
FOR(i, 0, N - 1) {
// if (!(C[i] <= i)) while (1) {}
while (C[i]++ < i) transaction(P[i]);
}
}
void solve() {
while (1) {
if (known == vector<bool>(N, 1)) return;
bool f = 0;
int k = -1;
ROF(i, N - 1, 0) {
if (!known[i]) f = 1;
else if (f) {k = i; break;}
}
if (mp.find(P[k] - 1) == mp.end()) {
query(P[k] - 1);
continue;
}
ll mn = 1e18;
for (auto [s, x] : res) mn = min(mn, x / (int)s.size());
query(mn);
}
}
// void solve(int S) {
// // assert(known[S]);
// bool all = 1;
// FOR(i, S, N - 1) if (!known[i]) all = 0;
// if (all) return;
// if (known[S + 1]) {
// solve(S + 1);
// return;
// }
// auto [s, x] = query(P[S] - 1);
// while (1) {
// for (auto [s, x] : res) if (s.size() == 1) know(*s.begin(), x);
// ROF(i, N - 1, S) if (known[i]) solve(i);
// while (1) {
// auto it = res.begin();
// while (it != res.end() && !(*it).first.empty()) it++;
// if (it == res.end()) break;
// res.erase(it);
// }
// bool duus = 1;
// for (auto [s, x] : res) if (!s.empty() && *s.rbegin() >= S && *s.begin() >= S) duus = 0;
// if (duus) break;
// ll mn = 1e18;
// for (auto [S, X] : res) {
// mn = min(mn, X / (int)S.size());
// }
// tie(s, x) = query(mn);
// }
// ROF(i, N - 1, S) if (known[i]) solve(i);
// }
void buy_souvenirs(int _N, long long P0) {
N = _N, P.resize(N), C.resize(N), known.resize(N);
know(0, P0);
solve();
buy_rest();
}
