#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=0; 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; int s=0,e=i; while(s+1<e) { int mid=(s+e)/2; if(query(mid,i-1).mx<d) { e=mid; } else{ s=mid; } } // cout<<"For "<<e<<' '<<i<<endl; cdp=query(e,i).dp+1; set(i); } cout<<query(1,n).dp<<endl; // for(int i=1;i<=n;i++) // { // int cu=0; // for(int j=i-1;j>=1;j--) // { // if(a[j]>=a[i]) // { // cu++; // } // else // { // if(cu>=d) // { // break; // } // cu=0; // dp[i]=max(dp[i],dp[j]+1); // } // } // } // int ans=0; // for(int i=1;i<=n;i++) // { // ans=max(ans,dp[i]); // } // cout<<ans<<endl; }