#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <cmath>
#define int long long
int LEN = 1; // Made LEN global
struct Node
{
int start;
int stop;
int cost;
int ind;
Node(int start, int stop, int cost, int ind) : start(start),
stop(stop), cost(cost), ind(ind) {};
Node() = default;
};
struct Query
{
int l, r;
int ser;
int gold;
int ind;
Query(int l, int r, int ser, int gold, int ind) : l(l), r(r), ser(ser), gold(gold), ind(ind) {};
Query() = default;
};
std::vector<int>
tin;
std::vector<int> order;
int T = 0;
void dfs(int v, std::vector<std::vector<Node>> &g, int pred = -1)
{
for (auto u : g[v])
{
if (u.stop != pred)
{
tin[u.stop] = order.size();
order.push_back(u.ind);
dfs(u.stop, g, v);
order.push_back(u.ind);
}
}
}
struct Corn
{
int n;
std::vector<int> a;
std::vector<int> sum;
std::vector<int> cnt;
int all;
Corn(int n) : n(n), all(0)
{
a.assign(n, 0);
int sz = (n + LEN - 1) / LEN + 2;
cnt.assign(sz, 0);
sum.assign(sz, 0);
}
void add(int i, int x)
{
all++;
assert(a[i] == 0);
a[i] += x;
sum[i / LEN] += x;
cnt[i / LEN]++;
}
void del(int i)
{
all--;
sum[i / LEN] -= a[i];
cnt[i / LEN]--;
a[i] = 0;
}
int need_gold(int ser)
{
int cnt1 = 0;
int ind = -1;
for (int i = 0; i < sum.size(); i++)
{
if (ser < sum[i])
{
ind = i;
break;
}
else
{
ser -= sum[i];
cnt1 += cnt[i];
}
}
if (ind == -1)
{
return 0;
}
for (int j = LEN * ind; j < std::min((int)a.size(),
(LEN) * (ind + 1));
j++)
{
if (a[j] != 0)
{
if (ser >= a[j])
{
ser -= a[j];
cnt1++;
}
else
