#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<vector <int> ,ll> pvl;
#define st first
#define nd second
const int maxn = 109;
ll P[maxn];
int ile[maxn];
int ng;
pvl zap(ll L)
{
pvl temp = transaction(L);
for(auto p : temp.st)
{
ile[p]++;
}
return temp;
}
void rek(vector <int> v , ll sum)
{
if(v.size() == 1)
{
P[v[0]] = sum;
if(v[0] == ng-1)return ;
if(P[v[0]+1] == 0)
{
pvl temp = zap(P[v[0]]-1);
rek(temp.st , P[v[0]]-1-temp.nd);
}
return ;
}
//cerr << "NEW: ";
//for(auto p : v )cerr << p << ' ' ; cerr << '\n';
//for(auto p : v )cerr << P[p] << ' ' ; cerr << '\n';
//cerr << " " << sum << endl;
//cerr <<"END\n";
vector <int> nv;
bool czyz = 0;
for(auto p : v)
{
if(P[p] != 0)
{
sum -= P[p];
czyz = 1;
}
else
{
nv.push_back(p);
}
}
if(czyz)
{
rek(nv,sum);
return ;
}
if(v.size() == 0)return ;
if(v.size() == 1)
{
P[v[0]] = sum;
return ;
}
ll sr = sum/(v.size());
pvl temp = zap(sr);
rek(temp.st , sr-temp.nd);
rek(v,sum);
}
void buy_souvenirs(int N, long long P0)
{
ng = N;
P[0] = P0;
for(int i = 1; i < N ; i++)
{
if(P[i] != 0)continue;
pvl temp = zap(P[i-1]-1);
rek(temp.st , P[i-1]-1-temp.nd);
}
for(int i = 1; i < N ; i++)
{
while(ile[i] < i)
{
zap(P[i]);
}
}
return;
}
/*
9
100 59 58 57 9 8 7 6 5
*/
