#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N=4e5; struct Data{ int len=0,pre=0,suf=0,mx=0,dp=0; }; Data seg[N<<2]; int n,a[N],cdp; Data merge(Data a,Data b) { Data c; c.mx=max(a.mx,max(b.mx,a.suf+b.pre)); c.pre=a.pre+b.pre*(a.len==a.pre); c.suf=b.suf+a.suf*(b.suf==b.len); c.len=a.len+b.len; c.dp=max(a.dp,b.dp); return c; } void build(int v=1,int l=1,int r=n) { if(l==r) { seg[v].pre=1; seg[v].len=1; seg[v].suf=1; seg[v].mx=1; seg[v].dp=0; return; } int m=(l+r)>>1; int lc=v<<1,rc=lc|1; build(lc,l,m); build(rc,m+1,r); seg[v]=merge(seg[lc],seg[rc]); } void set(int i,int v=1,int l=1,int r=n) { if(i<l or r<i)return; if(l==r) { seg[v].pre=0; seg[v].len=1; seg[v].suf=0; seg[v].mx=0; seg[v].dp=cdp; // cout<<"At "<<l<<' '<<r<<' '<<cdp<<endl; return; } int m=(l+r)>>1; int lc=v<<1,rc=lc|1; set(i,lc,l,m); set(i,rc,m+1,r); seg[v]=merge(seg[lc],seg[rc]); } Data iden; Data query(int ql,int qr,int v=1,int l=1,int r=n) { if(qr<l or r<ql) { return iden; } if(ql<=l and r<=qr) { return seg[v]; } int m=(l+r)>>1; int lc=v<<1,rc=lc|1; return merge(query(ql,qr,lc,l,m),query(ql,qr,rc,m+1,r)); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int d; cin>>n>>d; vector<pair<int,int>> ord; for(int i=1;i<=n;i++)cin>>a[i],ord.push_back({a[i],-i}); sort(begin(ord),end(ord)); build(); for(auto [x,i]:ord) { i=-i; cdp=0; set(i); int s=-1,e=i; while(s+1<e) { int mid=(s+e)/2; if(query(mid,i).mx<d) { e=mid; } else{ s=mid; } } cdp=query(e,i).dp+1; set(i); } cout<<query(1,n).dp<<endl; }