#include<bits/stdc++.h>
#include "koninc.h"
using namespace std;
const int nmax=3e5+42;
int n,k;
int inp[nmax];
int fenwick[nmax];
int query_fenwick(int pos)
{
int ret=0;
while(pos)
{
ret=ret+fenwick[pos];
pos=pos-(pos&(-pos));
}
return ret;
}
void update_fenwick(int pos)
{
while(pos<=n)
{
fenwick[pos]++;
pos=pos+(pos&(-pos));
}
}
struct info
{
int maxi,pos;
int lazy;
};
info tree[4*nmax];
info actual(info l)
{
l.maxi+=l.lazy;
l.lazy=0;
return l;
}
info my_merge(info l,info r)
{
l=actual(l);
r=actual(r);
if(l.maxi>=r.maxi)return l;
return r;
}
void push(int node)
{
tree[node*2].lazy+=tree[node].lazy;
tree[node*2+1].lazy+=tree[node].lazy;
tree[node].lazy=0;
}
void build(int node,int l,int r)
{
if(l==r)
{
tree[node].maxi=inp[l];
tree[node].pos=l;
tree[node].lazy=0;
return;
}
int av=(l+r)/2;
build(node*2,l,av);
build(node*2+1,av+1,r);
tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
void update_lazy(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)
{
tree[node].lazy++;
return;
}
push(node);
int av=(l+r)/2;
if(lq<=av)update_lazy(node*2,l,av,lq,min(av,rq));
if(av<rq)update_lazy(node*2+1,av+1,r,max(av+1,lq),rq);
tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
void update_idle(int node,int l,int r,int pos)
{
if(l==r)
{
tree[node].maxi=-1e9;
tree[node].pos=0;
tree[node].lazy=0;
return;
}
push(node);
int av=(l+r)/2;
if(pos<=av)update_idle(node*2,l,av,pos);
else update_idle(node*2+1,av+1,r,pos);
tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
void podlej(int a, int b)
{
a++;
b++;
update_lazy(1,1,n,a,b);
while(1)
{
info current=actual(tree[1]);
if(current.maxi<k)return;
update_fenwick(current.pos);
update_idle(1,1,n,current.pos);
}
}
void inicjuj(int n_,int k_,int *D)
{
n=n_;
k=k_;
for(int i=1;i<=n;i++)
inp[i]=D[i-1];
k++;
build(1,1,n);
podlej(0,n-1);
}
int dojrzale(int a, int b)
{
a++;
b++;
return query_fenwick(b)-query_fenwick(a-1);
}
/*
int D[4]={5,4,3,7};
int main()
{
inicjuj(4, 6, D);
cout<<dojrzale(2, 3)<<endl;//1
podlej(0, 2);
cout<<dojrzale(1, 2)<<endl;//0
podlej(2, 3);
podlej(0, 1);
cout<<dojrzale(0, 3)<<endl;//3
return 0;
}
*/
