#include <bits/stdc++.h>
#include "biscuits.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int H = 60;
const ll N = (1LL<<(ll)H);
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int NN = 1000 * 1000 + 7;
ll drz[NN], il[NN];
int l[NN], r[NN]; int cnt;
ll answer = 0LL;
void Init()
{
for(int i = 1; i <= 4000; ++i)
{
drz[i] = 0LL; l[i] = 0; r[i] = 0;
}
for(int i = 1; i <= H; ++i)
{l[i] = i + 1; drz[i] = 1LL;}
drz[H + 1] = 1LL;
cnt = H + 1;
}
void Copy(int v1, int v2, ll a, ll b, ll lim)
{
if((a + b) / 2LL <= lim)
l[v2] = l[v1];
if((a + b) / 2LL > lim)
{
if(l[v1] != 0)
{
++cnt; l[v2] = cnt;
Copy(l[v1], l[v2], a, (a + b) / 2LL, lim);
}
}
if((a + b) / 2LL < lim)
{
if(r[v1] != 0)
{
++cnt; r[v2] = cnt;
Copy(r[v1], r[v2], (a + b) / 2LL + 1LL, b, lim);
}
}
//cerr << v2 << " Copy " << l[v2] << " " << r[v2] << "\n";
drz[v2] = drz[l[v2]] + drz[r[v2]];
}
void Upd(ll b, ll lim)
{
int v1;
ll ran = (N - 1LL) / 2LL;
v1 = 1;
while(ran + 1LL > b)
{
ran /= 2LL; v1 = l[v1];
}
//cerr << b << " " << "Upd: " << v1 << " " << ran << " " << lim << "\n";
if(lim >= b - 1LL)
{
r[v1] = l[v1];
}else
{
++cnt;
r[v1] = cnt;
//cerr << "cp " << l[v1] << " " << r[v1] << "\n";
Copy(l[v1], r[v1], 0, ran, lim);
}
while(v1 > 0)
{
drz[v1] = drz[l[v1]] + drz[r[v1]];
--v1;
}
}
long long count_tastiness(long long x, vector<long long> _a)
{
Init();
int n = _a.size() - 1;
for(int i = 0; i <= n; ++i)
il[i] = _a[i];
if(il[0] >= x)
Upd(1LL, 0LL);
//cerr << "DP: \n";
for(int i = 1; i <= 60; ++i)
{
if(x * (1LL<<(ll)i) > (ll)I) break;
il[i] *= (1LL<<(ll)i);
ll ned = max(0LL, (x * (1LL<<(ll)i) - il[i]));
ll lim = (il[i - 1] - ned) / x;
if(il[i - 1] - ned < 0LL)
lim = -1LL;
lim = min(lim, (1LL<<(ll)(i)) - 1LL);
//cerr << i << " " << "bis: " << ned << " " << lim << "\n";
if(lim >= 0LL)
Upd((1LL<<(ll)i), lim);
il[i] += il[i - 1];
//cerr << drz[1] << "\n";
}
for(int i = 0; i <= 100; ++i)
il[i] = 0LL;
return drz[1];
}
