#include "souvenirs.h"
#include <bits/stdc++.h>
#define task "TEST"
#define task2 "A"
#define pl pair<ll, ll>
#define pf push_front
#define pb push_back
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b, c) for (int i=a; i<=b; i+=c)
#define FORE(i, a, b, c) for (int i=a; i>=b; i+=c)
using namespace std;
using ll = long long;
using Knowledge = pair<vector<int>, ll>;
using ull = unsigned long long;
const int Mod = 998244353;
const int maxn = 1e3;
const ll Inf = 1e16;
Knowledge res;
ll P[maxn+1], num[maxn+1], n, A[maxn+1];
map <ll, Knowledge> Data;
/*Knowledge transaction(ll val){
vector<int> a; a.clear();
ll sum = val;
FOR(i, 0, n-1, 1) {
if (sum >= A[i]) {
a.pb(i); sum -= A[i];
}
}
return mp(a, sum);
}*/
Knowledge Fix(Knowledge know) {
FOR(i, 0, (ll)know.fi.size()-1, 1) {
ll p = know.fi[i];
if (P[p] == 0) continue;
know.fi.erase(know.fi.begin() + i);
know.se -= P[p]; i--;
}
return know;
}
Knowledge Add(ll val) {
//cerr << val << " ";
res = transaction(val);
for (auto p : res.fi) num[p]++;
res.se = val - res.se;
return res;
}
void Sub6(ll n) {
priority_queue<ll, vector<ll>, greater<ll>> PQ;
PQ.push(P[0] - 1);
while (!PQ.empty()) {
ll v = PQ.top(); PQ.pop();
if (!Data.count(v)) Data[v] = Add(v);
Knowledge res = Fix(Data[v]);
if (res.fi.size() == 1) {
ll p = res.fi[0]; P[p] = res.se;
if (P[p] != 0) continue;
if (p + 1 < n and !P[p + 1]) PQ.push(P[p] + 1);
}
else {
PQ.push(v);
PQ.push(res.se/res.fi.size());
}
}
FOR(i, 1, n-1, 1) FOR(j, num[i], i-1, 1)
Add(P[i]);
}
void buy_souvenirs(int n, long long P0) {
P[0] = P0; Sub6(n);
}
/*int main() {
cin >> n;
FOR(i, 0, n-1, 1) cin >> A[i];
buy_souvenirs(n, A[0]);
FOR(i, 0, n-1, 1) cerr << num[i] << " ";
}*/
