#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i=a; i<(b); ++i)
#define all(a) begin(a), end(a)
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define pb push_back
template<typename T> using v = vector<T>;
template<typename T> using vv = v<vector<T>>;
typedef long long ll;
typedef pair<ll ,ll > pii;
typedef v<int> vi;
//Represent y as a subset of indices
//yi = {0,x}
//a0 >= y0
//a1 + a0/2 >= y1 + y0/2
//a2 + a1/2 + a0 >= y2 + y1/2 + y0/4
//...
//mutiply the ith eqn by 2^i, we get
//a0 >= y0
//2a1 + a0 >= 2y1 + y0
//4a2 + 2a1 + a0 >= 4y2 + 2y1 + y0
//2^k*ak + .... + a0 >= 2^k*yk + ... y0
//Let S = set of possible values of y0+2y1+4y2 + ... 2^i * yi
//after processing a0 to ai
//we need to do two things
//1) S = S U 2^i * x
//2) truncate S by p(i) = sum_j<=i 2^j * aj
struct node{
ll sum = 0;
node * L = NULL;
node * R = NULL;
node(){}
node(node *v){
L = v->L;
R = v->R;
sum = v->sum;
}
};
node* del(node *v,ll k,ll lvl){
node *u = new node(v);
if(k == (1LL<<lvl))return u; //keep everything
if(k == 0)return NULL; //destroy everything
//cout<<k<<" "<<lvl<<" "<<u->sum<<'\n';
if(k > (1LL<<(lvl-1))){
if(u->R)u->R = del(u->R,k-(1LL<<(lvl-1)),lvl-1);
}else{
u->R = NULL;
if(u->L)u->L = del(u->L,k,lvl-1);
}
u->sum = 0;
if(u->L)u->sum += u->L->sum;
if(u->R)u->sum += u->R->sum;
//cout<<k<<" "<<lvl<<" "<<u->sum<<'\n';
return u;
}
const ll INF = 2e18;
ll count_tastiness(ll x, vector<ll> a) {
ll k = sz(a);
vector<ll>p(60,0);
for(int i=0;i<k;i++)p[i] = a[i]* (1LL<<i);
for(int i=1;i<60;i++)p[i] += p[i-1];
for(ll &v:p)v/=x;
//for(ll v:p)cout<<v<<" ";
//cout<<'\n';
node *root = new node();
root->sum = 1;
for(ll i=0;i<60;i++){
node *nroot = new node();
nroot->L = new node(root);
nroot->R = new node(root);
nroot->sum = 2*root->sum;
root = nroot;
root = del(root,p[i]+1,i+1);
}
return root->sum;
}
