#include "biscuits.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
ll count_tastiness(ll x, vector<ll> a)
{
while (a.size() <= 60)
a.push_back(0);
ll s[61];
s[60] = 0;
pair<ll, ll>s1[61];
s1[60] = {0, 0};
for (int i = 59; i >= 0; i--)
{
s[i] = a[i] + s[i + 1] * 2;
if (s[i] >= 3 * x)
s[i] = 3 * x;
s1[i].first = s1[i + 1].first * 2;
s1[i].second = s1[i + 1].second * 2 + a[i];
ll d = s1[i].second / x;
s1[i].second -= x * d;
s1[i].first += d;
s1[i].first = min(s1[i].first, 4000000000000000000ll);
}
map<ll, ll, greater<ll>>M[61];
function<ll(ll, int)>get = [&](ll d, int i)->ll
{
if (i == 60)
return d / x + 1;
if (s[i] + d < x)
return 1;
if (s[i] + d < 2 * x)
{
if (a[i] + d >= x)
return 2;
else
return 1;
}
if (s[i] + d < 3 * x)
{
ll ret = 1;
if (a[i] + d >= x)
ret++;
if ((a[i] + d) / 2 + a[i + 1] >= x)
ret++;
return ret;
}
ll mx = s1[i].first + 1;
if (s1[i].second + d >= x)
mx++;
auto it = M[i].lower_bound(d);
if (it != M[i].end() && (it->second == mx || it->first == d))
return it->second;
if (a[i] + d < x)
{
return M[i][d] = get((d + a[i]) / 2, i + 1);
}
else
{
return M[i][d] = get((d + a[i]) / 2, i + 1) + get((d + a[i] - x) / 2, i + 1);
}
};
return get(0, 0);
}
