#include "biscuits.h"
#include <iostream>
using namespace std;
using ll = long long;
vector<pair<ll, ll>> unite_same(vector<pair<ll, ll>>& vcnts) {
vector<pair<ll, ll>> ans;
for (auto p : vcnts) {
if (ans.empty() || ans.back().first < p.first)
ans.push_back(p);
else
ans.back().second += p.second;
}
return ans;
}
vector<pair<ll, ll>> merge(vector<pair<ll, ll>>& a, vector<pair<ll, ll>>& b) {
int n = a.size();
int m = b.size();
int j = 0;
vector<pair<ll, ll>> ans;
for (int i = 0; i < n; ++i) {
while (j < m && b[j].first <= a[i].first) {
ans.push_back(b[j]);
++j;
}
if (ans.size() && ans.back().first == a[i].first)
ans.back().second += a[i].second;
else
ans.push_back(a[i]);
}
while (j < m) {
ans.push_back(b[j]);
++j;
}
return ans;
}
ll count_tastiness(ll x, vector<ll> a) {
int k = a.size();
vector<pair<ll, ll>> vcnts;
vcnts.push_back({0, 1});
for (int i = 0; i < 60; ++i) {
for (auto& [t, cnt] : vcnts) {
t >>= 1;
if (i < k)
t += a[i];
}
vcnts = unite_same(vcnts);
if (vcnts.back().first < x)
continue;
vector<pair<ll, ll>> addv;
for (auto p : vcnts) {
if (p.first >= x)
addv.push_back({p.first - x, p.second});
}
vcnts = merge(vcnts, addv);
}
ll ans = 0;
for (auto [t, cnt] : vcnts)
ans += cnt;
return ans;
}
