WA on #7 #8 #10

#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
#define gcd(x,y) (__gcd((x),(y)))
#define lcm(x,y) ((x)*(y)/gcd((x),(y)))
#define lg(x,y)  (__lg((x),(y)))
using namespace std;
 
namespace FastIO
{
    template<typename T=int> inline T read()
    {
        T s=0,w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        return s*w;
    }
    template<typename T> inline void read(T &s)
    {
        s=0; int w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        s=s*w;
    }
    template<typename T,typename... Args> inline void read(T &x,Args &...args)
    {
        read(x),read(args...);
    }
    template<typename T> inline void write(T x,char ch)
    {
        if(x<0) x=-x,putchar('-');
        static char stk[25]; int top=0;
        do {stk[top++]=x%10+'0',x/=10;} while(x);
        while(top) putchar(stk[--top]);
        if(ch!='~') putchar(ch);
        return;
    }
}
using namespace FastIO;
 
inline void file()
{
//    freopen(".in","r",stdin);
    freopen("11.out","w",stdout);
    return;
}
 
bool Mbe;
 
namespace wycyyy
{
    static const int MAX=100010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    static const int mod=1e9+7;
    static const int bas=131;
    
    int m,ans=-INF,f[MAX][30];
    
    namespace SA
    {
    	static const int Sigma=127;
    	int rk[MAX],olrk[MAX],sa[MAX],buc[MAX];
    	int id[MAX],pid[MAX],height[MAX];
    	int s[MAX]; int n;
    	
    	inline void Build()
    	{
    		for(int i=1;i<=n;++i) ++buc[rk[i]=s[i]];
    		for(int i=1;i<=Sigma;++i) buc[i]+=buc[i-1];
    		for(int i=n;i;--i) sa[buc[rk[i]]--]=i;
    		for(int w=1,m=Sigma,p=0;;w<<=1,m=p,p=0)
    		{
    			for(int i=n;i+w>n;--i) id[++p]=i;
    			for(int i=1;i<=n;++i) if(sa[i]>w) id[++p]=sa[i]-w;
    			for(int i=1;i<=m;++i) buc[i]=0;
    			for(int i=1;i<=n;++i) ++buc[pid[i]=rk[id[i]]];
    			for(int i=1;i<=m;++i) buc[i]+=buc[i-1];
    			for(int i=n;i;--i) sa[buc[pid[i]]--]=id[i];
    			p=0;
    			for(int i=1;i<=n;++i) olrk[i]=rk[i];
    			for(int i=1;i<=n;++i) p+=(olrk[sa[i]]!=olrk[sa[i-1]]||olrk[sa[i]+w]!=olrk[sa[i-1]+w]),rk[sa[i]]=p;
    			if(p==n) break;
			}
		}
		inline void GetHeight()
		{
			for(int i=1,k=0;i<=n;++i)
			{
				for(k=max(k-1,0ll);s[i+k]==s[sa[rk[i]-1]+k];++k);
				height[rk[i]]=k;
			}
		}
	}
	using namespace SA;
    
    inline void mian()
    {
    	auto query=[&](int l,int r)->int
    	{
			int len=__lg(r-l+1);
			return max(f[l][len],f[r-(1<<len)+1][len]);
		};
    	
    	read(n,m);
		for(int i=1;i<=n;++i) s[i]=read();
    	Build(),GetHeight();
    	for(int i=1;i<=n;++i) f[i][0]=height[i];
    	for(int i=1;i<=__lg(n);++i) for(int j=1;j+(1<<i)-1<=n;++j) f[j][i]=min(f[j][i-1],f[j+(1<<i>>1)][i-1]);
    	for(int i=2;i+m-2<=n;++i) cmax(ans,query(i,i+m-2));
    	write(ans,'\n');
    }
}

bool Med;

signed main()
{
//  file();
    fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
    int Tbe=clock();
    wycyyy::mian();
    int Ted=clock();
    cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
    return (0-0);
}