#include "biscuits.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node{
ll cnt;
int lc, rc;
Node(){
cnt = 0;
lc = rc = -1;
}
};
ll count_tastiness(ll x, vector<ll>a){
while(a.size() < 60){
a.push_back(0);
}
for(int i = 1; i < 60; i++){
a[i] = (a[i] << i) + a[i - 1];
}
for(ll& v : a){
v /= x;
}
vector<ll>ans(1, 0);
int root = 0;
vector<Node>st;
st.push_back(Node());
st[0].cnt = 1;
function<void(int, ll, ll, ll, ll)>fill_zero;
fill_zero = [&] (int id, ll l, ll r, ll u, ll v){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
st[id] = Node();
return;
}
ll m = (l + r) >> 1;
if(st[id].lc != -1){
st.push_back(st[st[id].lc]);
fill_zero(st[id].lc = int(st.size()) - 1, l, m, u, v);
}
if(st[id].rc != -1){
st.push_back(st[st[id].rc]);
fill_zero(st[id].rc = int(st.size()) - 1, m + 1, r, u, v);
}
st[id].cnt = (st[id].lc == -1 ? 0 : st[st[id].lc].cnt) + (st[id].rc == -1 ? 0 : st[st[id].rc].cnt);
};
for(int bit = 0; bit < 60; bit++){
int right_node = st.size();
st.push_back(st[root]);
fill_zero(right_node, 1LL << bit, (1LL << (bit + 1)) - 1, max(1LL << bit, a[bit] + 1), (1LL << (bit + 1)) - 1);
int new_root = st.size();
st.push_back(Node());
st[new_root].cnt = st[st[new_root].lc = root].cnt + st[st[new_root].rc = right_node].cnt;
root = new_root;
}
return st[root].cnt;
}
