#include "souvenirs.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
//void __print(int x) {std::cerr << x;}
//void __print(long x) {std::cerr << x;}
//void __print(long long x) {std::cerr << x;}
//void __print(unsigned x) {std::cerr << x;}
//void __print(unsigned long x) {std::cerr << x;}
//void __print(unsigned long long x) {std::cerr << x;}
//void __print(float x) {std::cerr << x;}
//void __print(double x) {std::cerr << x;}
//void __print(long double x) {std::cerr << x;}
//void __print(char x) {std::cerr << '\'' << x << '\'';}
//void __print(const char *x) {std::cerr << '\"' << x << '\"';}
//void __print(const std::string &x) {std::cerr << '\"' << x << '\"';}
//void __print(bool x) {std::cerr << (x ? "true" : "false");}
//template<typename T, typename V>
//void __print(const std::pair<T, V> &x) {std::cerr << '{'; __print(x.first); std::cerr << ','; __print(x.second); std::cerr << '}';}
//template<typename T>
//void __print(const T &x) {int f = 0; std::cerr << '{'; for(auto &i: x) std::cerr << (f++? "," : ""), __print(i); std::cerr << "}";}
//void _print() {std::cerr << "]\n";}
//template <typename T, typename... V>
//void _print(T t, V... v) {__print(t); if(sizeof...(v)) std::cerr << ", "; _print(v...);}
//#ifndef ONlINE_JUDGE
//#define debug(x...) std::cerr << "[" << #x << "] = ["; _print(x)
//#else
//#define debug(x...)
//#endif
//
//int totelements;
//std::vector<long long> r;
//
//std::pair<std::vector<int>, long long> transaction(long long m) {
// std::vector<int> res;
// for(int i = 0; i < totelements; i++) {
// if(r[i] <= m) {
// res.push_back(i);
// m -= r[i];
// }
// }
// return {res, m};
//}
int n;
std::map<long long, std::pair<std::vector<int>, long long>> trans;
std::vector<long long> costs;
std::vector<int> counts;
void recurse(std::vector<int> elements, long long sum) {
// debug(elements);
// debug(costs);
// debug(counts);
std::set<int> need;
for(auto e : elements) need.insert(e);
while(!need.empty()) {
int denom = (int)elements.size();
if(denom == 1) {
if(elements[0] == n-1) costs[n-1] = sum;
else {
long long prev = sum;
if(!costs[elements[0]]) {
if(costs[elements[0]+1]) {
costs[elements[0]] = sum;
return;
}
if(trans.find(prev-1) == trans.end()) {
trans[prev-1] = transaction(prev-1);
// debug(trans[prev-1].first);
trans[prev-1].second = prev-1-trans[prev-1].second;
for(auto q : trans[prev-1].first) ++counts[q];
}
std::pair<std::vector<int>, long long> temp = trans[prev-1];
std::pair<std::vector<int>, long long> res;
res.second = temp.second;
for(auto q : temp.first) {
if(costs[q]) res.second -= costs[q];
else res.first.push_back(q);
}
if(res.first.empty()) {
costs[elements[0]] = sum;
return;
}
recurse(res.first, res.second);
costs[elements[0]] = sum;
}
}
return;
} else {
long long query = sum/denom;
if(trans.find(query) == trans.end()) {
trans[query] = transaction(query);
// debug(trans[query].first);
trans[query].second = query-trans[query].second;
for(auto q : trans[query].first) ++counts[q];
}
std::pair<std::vector<int>, long long> temp = trans[query];
std::pair<std::vector<int>, long long> res;
//RE, figure out why INF looping
res.second = temp.second;
for(auto q : temp.first) {
if(costs[q]) res.second -= costs[q];
else res.first.push_back(q);
}
if(res.first.empty()) return;
recurse(res.first, res.second);
for(auto i : elements) {
if(costs[i]) need.erase(i);
}
std::vector<int> etemp;
for(auto e : elements) {
if(costs[e]) sum -= costs[e];
else etemp.push_back(e);
}
elements = etemp;
if(elements.size() == 1) {
if(elements[0] != n-1 && !costs[elements[0]+1]) continue;
else costs[elements[0]] = sum;
return;
}
}
}
// debug(costs);
}
void buy_souvenirs(int N, long long p0) {
n = N;
costs.resize(n, 0);
counts.resize(n, 0);
costs[0] = p0;
std::set<int> need;
for(int i = 1; i < n; ++i) need.insert(i);
while(!need.empty()) {
int prev = *need.begin()-1;
if(trans.find(costs[prev]-1) == trans.end()) {
trans[costs[prev]-1] = transaction(costs[prev]-1);
// debug(trans[costs[prev]-1].first);
trans[costs[prev]-1].second = costs[prev]-1-trans[costs[prev]-1].second;
for(auto q : trans[costs[prev]-1].first) ++counts[q];
}
std::pair<std::vector<int>, long long> temp = trans[costs[prev]-1];
std::pair<std::vector<int>, long long> res;
res.second = temp.second;
for(auto q : temp.first) {
if(costs[q]) res.second -= costs[q];
else res.first.push_back(q);
}
recurse(res.first, res.second);
for(int i = 1; i < n; ++i) {
if(costs[i]) need.erase(i);
}
}
for(int i = 1; i < n; ++i) {
for(int j = counts[i]; j < i; ++j) transaction(costs[i]);
}
// debug(costs);
// debug(counts);
}
//int main() {
// std::cin >> totelements;
// r.resize(totelements);
// for(int i = 0; i < totelements; i++) std::cin >> r[i];
// buy_souvenirs(totelements, r[0]);
//}
