#include "biscuits.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int K = 130;
vector<pll> dif[K];
ll cnt[K];
ll x;
ll f(int i, ll x)
{
auto it = upper_bound(dif[i].begin(), dif[i].end(), pll{x, 2e18});
--it;
return it->second;
}
ll f_next(int i, ll x)
{
ll val = 0;
val += f(i+1, cnt[i+1] + x/2);
if (x>=::x) {
ll mv = x-::x;
val += f(i+1, cnt[i+1] + mv/2);
}
return val;
}
ll get_next(int i, ll pre, ll pre_val)
{
ll l = pre+1;
ll r = 2*x+2;
while (l<r) {
ll mid = (l+r)/2;
ll val = f_next(i, mid);
if (val > pre_val)
r = mid;
else
l = mid+1;
}
return l;
}
long long count_tastiness(long long x, std::vector<long long> a)
{
::x = x;
Loop (i,0,a.size())
cnt[i] = a[i];
Loop (i,a.size(),K)
cnt[i] = 0;
Loop (i,0,K-1) {
ll mv = cnt[i]-x;
if (mv <= 1)
continue;
mv &= -2;
cnt[i] -= mv;
cnt[i+1] += mv/2;
}
dif[K-1] = {{0, 1}, {x, 2}, {2*x, 3}};
LoopR (i,0,K-1) {
ll pre = 0, pre_val = f(i+1, cnt[i+1]);
dif[i] = {{pre, pre_val}};
for (;;) {
ll nxt = get_next(i, pre, pre_val);
if (nxt == 2*x+2)
break;
pre = nxt;
pre_val = f_next(i, nxt);
//printf("%d %ld %ld\n", i, pre, pre_val);
dif[i].push_back({pre, pre_val});
}
}
return f(0, cnt[0]);
}
