#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 II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
ll il[N];
vector<pair<ll, ll>> zbi; ll answer = 0LL;
void Upd(ll b, ll lim)
{
vector<pair<ll, ll>> nxt;
for(int i = 0; i < (int)zbi.size() && (zbi[i].st <= lim); ++i)
{
pair<ll, ll> nw = make_pair(b + zbi[i].st, b + min(lim, zbi[i].nd));
answer += nw.nd - nw.st + 1LL;
nxt.pb(nw);
}
if((int)nxt.size() > 0)
{
int i = (int)zbi.size() - 1;
if(zbi[i].nd + 1LL == nxt[0].st)
{
nxt[0].st = zbi[i].st;
zbi.pop_back();
}
}
for(int i = 0; i < (int)nxt.size(); ++i)
zbi.pb(nxt[i]);
}
long long count_tastiness(long long x, vector<long long> _a)
{
zbi.clear(); answer = 0LL;
int n = _a.size() - 1;
for(int i = 0; i <= n; ++i)
il[i] = _a[i];
if(il[0] >= x)
{
answer += 2LL;
zbi.pb(make_pair(0LL, 1LL));
}
else
{
answer += 1LL;
zbi.pb(make_pair(0LL, 0LL));
}
//cerr << "DP: \n";
for(int i = 1; i <= 20; ++i)
{
if(x * (1LL<<(ll)i) > (ll)II) break;
il[i] *= (1LL<<(ll)i);
ll ned = max(0LL, (x * (1LL<<(ll)i) - il[i]));
ll lim = (il[i - 1] - ned) / x;
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];
}
for(int i = 0; i <= 100; ++i)
il[i] = 0LL;
return answer;
}
