#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=3e5+5,MAXM=40,INF=1e9,MOD=1e9+7;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define pb push_back
#define endl "\n"
#define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush;
#define PRINTBITS(x) {bitset<5> f=x; cerr<<#x<<'-'<<f<<endl<<flush;}
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
ll N,m,K,q,x,y,z,res=0,l,r;
string s,t;
vector<int> a;
int lazy[4*MAXN];
pii seg[4*MAXN]; // cuvacu par gde je druga vrdnost index maximuma
int drvece[4*MAXN];
void propagate(int node,int l,int r){
seg[node].fi+=lazy[node];
if(l<r){
lazy[2*node]+=lazy[node];
lazy[2*node+1]+=lazy[node];
}
lazy[node]=0;
}
void update(int node,int l,int r,int L,int R,int val){
propagate(node,l,r);
if(l>r || l>R || r<L) return;
if(L<=l && r<=R){
lazy[node]+=val;
propagate(node,l,r);
return;
}
update(2*node,l,mid,L,R,val);
update(2*node+1,mid+1,r,L,R,val);
seg[node]=max(seg[2*node],seg[2*node+1]);
}
pii query(int node,int l,int r,int L,int R){
propagate(node,l,r);
if(l>r || l>R || r<L) return {-INF,-INF};
if(L<=l && r<=R) return seg[node];
return max(query(2*node,l,mid,L,R),query(2*node+1,mid+1,r,L,R));
}
void updateDrvece(int node,int l,int r,int idx){
if(l==r){
drvece[node]++;
return;
}
if(idx<=mid) updateDrvece(2*node,l,mid,idx);
else updateDrvece(2*node+1,mid+1,r,idx);
drvece[node]=drvece[2*node]+drvece[2*node+1];
}
int queryDrvece(int node,int l,int r,int L,int R){
if(L<=l && r<=R) return drvece[node];
int ret=0;
if(L<=mid) ret+=queryDrvece(2*node,l,mid,L,R);
if(R>mid) ret+=queryDrvece(2*node+1,mid+1,r,L,R);
return ret;
}
void init(int node,int l,int r){
if(l==r){
if(a[l]>=K){
seg[node]={-INF,-INF};
updateDrvece(1,1,N,l);
}
else{
seg[node]={a[l],l};
}
return;
}
init(2*node,l,mid); init(2*node+1,mid+1,r);
seg[node]=max(seg[2*node],seg[2*node+1]);
}
void inicjuj(int n, int k, int *D){
K=k;
N=n;
a.pb(INF);
for(int i=1;i<=N;i++){
a.pb(D[i-1]);
}
init(1,1,N);
}
void podlej(int a, int b){
++a; ++b;
update(1,1,N,a,b,+1);
while(seg[1].fi>=K){
updateDrvece(1,1,N,seg[1].se);
update(1,1,N,seg[1].se,seg[1].se,-INF);
}
}
int dojrzale(int a, int b){
++a; ++b;
return queryDrvece(1,1,N,a,b);
}
