#include <bits/stdc++.h>
using namespace std;
const int NMAX=3e5;
int aib[NMAX+5], n, a[NMAX+5];
class SegTree
{
public:
pair <int, int> t[6*NMAX+5];
int f[6*NMAX+5];
int limst=0, limdr=0;
void lazy (int nod)
{
if (f[nod]==0)
return;
t[nod].first+=f[nod];
f[nod*2]+=f[nod];
f[nod*2+1]+=f[nod];
f[nod]=0;
}
void actbuild (int nod, int st, int dr)
{
if (st==dr)
t[nod]={0, st};
else
{
int mij = (st+dr) >> 1;
actbuild (nod*2, st, mij);
actbuild (nod*2+1, mij+1, dr);
t[nod]=min (t[nod*2], t[nod*2+1]);
}
}
void build (int st, int dr)
{
limst=st;
limdr=dr;
actbuild (1, limst, limdr);
}
void actupdate (int nod, int st, int dr, int stq, int drq, int val)
{
lazy (nod);
if (stq<=st && dr<=drq)
{
f[nod]+=val;
lazy (nod);
}
else
{
lazy (nod*2);
lazy (nod*2+1);
int mij = (st+dr) >> 1;
if (drq<=mij)
actupdate (nod*2, st, mij, stq, drq, val);
else if (stq>mij)
actupdate (nod*2+1, mij+1, dr, stq, drq, val);
else actupdate (nod*2, st, mij, stq, drq, val), actupdate (nod*2+1, mij+1, dr, stq, drq, val);
t[nod]=min (t[nod*2], t[nod*2+1]);
}
}
void update (int st, int dr, int val)
{
actupdate (1, limst, limdr, st, dr, val);
}
};
SegTree aint;
void updateAib (int x, int val)
{
for (int i=x;i<=n;i+=(i&-i))
aib[i]+=val;
}
int queryAib (int x)
{
int ret=0;
for (int i=x;i>0;i-=(i&-i))
ret+=aib[i];
return ret;
}
void inicjuj (int N, int k, int *d)
{
n=N;
for (int i=0;i<=n;i++)
aib[i]=0;
aint.build (1, n);
for (int i=0;i<n;i++)
{
a[i+1]=k-d[i];
}
for (int i=1;i<=n;i++)
{
if (a[i]<=0)
{
updateAib (i, 1);
aint.update (i, i, 1e8);
}
else
{
aint.update (i, i, a[i]);
}
}
}
void podlej (int st, int dr)
{
st++;
dr++;
aint.update (st, dr, -1);
}
int dojrzale (int st, int dr)
{
st++;
dr++;
aint.lazy (1);
while (aint.t[1].first<=0)
{
updateAib (aint.t[1].second, 1);
aint.update (aint.t[1].second, aint.t[1].second, 1e8);
}
return queryAib (dr)-queryAib (st-1);
}
