#include <bits/stdc++.h>
using namespace std;
//#define int long long
/*
vector<int>a;
pair<vector<int>,int>transaction(int num){
vector<int>ans;
for(int i=0;i<a.size();i++){
if(num>=a[i]){
ans.push_back(i);
num-=a[i];
}
}return {ans,num};
}*/
pair<vector<int>,long long>transaction(long long cost);
void to_buy(int ind,long long cost,vector<long long>&vals,vector<int>&cant){
pair<vector<int>,long long>ans = transaction(cost);
for(auto it : ans.first)cant[it]++;
if(ans.first.size()==1){
vals[ind]=cost-ans.second;
}else{
reverse(ans.first.begin(),ans.first.end());
long long nxt = 0;
for(auto it : ans.first){
if(vals[it]==-1)to_buy(it,(cost+1LL*(ans.first.size()-1))/(1LL*ans.first.size()),vals,cant);
nxt+=vals[it];
}vals[ind]=cost-nxt;
}return;
}
void buy_souvenirs(int N, long long P0){
vector<long long>vals(N,-1);
vector<int>cant(N,0);
vals[0]=P0;
for(int i=1;i<N;i++){
if(vals[i]==-1){
to_buy(i,vals[i-1]-1,vals,cant);
}
}
for(int i=0;i<N;i++){
if(cant[i]>i)cout << "BBBBAAAAAAAAD\n";
else{
while(cant[i]<i){
transaction(vals[i]);
cant[i]++;
}
}
}return;
}
/*
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
const int MAXI = 100000;
while(t--){
int n = rand()%100;
a.resize(n);
for(int i=0;i<n;i++){
a[i] = rand()%MAXI;
}
sort(a.begin(),a.end());
auto it = unique(a.begin(),a.end());
int x = 0;
while(it!=a.end()){
(*it) = MAXI+x;
x++;
it++;
}
sort(a.begin(),a.end());
buy_souvenirs(n,a[0]);
a.clear();
}
return 0;
}*/
