#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
set<pii>::iterator addInterval(set<pii>& is, ll L, ll R) {
if (L == R) return is.end();
auto it = is.lower_bound({L, R}), before = it;
while (it != is.end() && it->first <= R) {
R = max(R, it->second);
before = it = is.erase(it);
}
if (it != is.begin() && (--it)->second >= L) {
L = min(L, it->first);
R = max(R, it->second);
is.erase(it);
}
return is.insert(before, {L,R});
}
void removeInterval(set<pii>& is, ll L, ll R) {
if (L == R) return;
auto it = addInterval(is, L, R);
auto r2 = it->second;
if (it->first == L) is.erase(it);
else (int&)it->second = L;
if (R != r2) is.emplace(R, r2);
}
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;
set<pii>s;
s.insert({0,1});
for(int i=0;i<60;i++){
auto it = s.end();
it--;
while(!s.empty() && it->se > p[i]+1){
ll l = it->fi;
ll r = it->se;
s.erase(it);
removeInterval(s,l,r);
if(l < p[i]+1){
addInterval(s,l,p[i]+1);
}
it = s.end();
it--;
}
//cout<<"i: "<<i<<'\n';
//for(auto [l,r]:s)cout<<l<<" "<<r<<'\n';
vector<pii>t;
for(auto [l,r]:s){
ll L = l + (1LL<<i);
ll R = r + (1LL<<i);
R = min(R,p[i]+1);
if(L>=R)continue;
t.push_back({L,R});
}
for(auto [l,r]:t)addInterval(s,l,r);
//cout<<"i: "<<i<<'\n';
//for(auto [l,r]:s)cout<<l<<" "<<r<<'\n';
}
ll ans = 0;
for(auto [l,r]:s)ans += r-l;
return ans;
}
