#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=2100000000,N=6e5+5,K=30+5;
int n,k;
int f[K][N],lasf[N],lasb[N],st[N];
int calc(int p[],int i,int &tp)
{
	while(tp&&p[i]>p[st[tp]])
		--tp;
	st[++tp]=i;
	return st[tp-1];
}
int a[N];
int work(int p[])
{
	memset(f,0,sizeof(f));
	for(int i=1,tp=0; i<=n; ++i)
		lasf[i]=calc(p,i,tp);
	for(int i=n,tp=0; i>=1; --i)
		lasb[i]=calc(p,i,tp);
	for(int i=1; i<=k; ++i)
	{
		for(int j=1; j<=n; ++j)
			a[j]=f[i-1][j-1]+1;
		for(int j=1; j<=n; ++j)
			a[j]=max(a[j],a[j-1]);
		for(int j=1; j<=n; ++j)
			if(lasf[j])
				a[j]=max(a[j],a[lasf[j]]+1);
		for(int j=1; j<=n; ++j)
			f[i][j]=max(f[i][j],a[j]);

		for(int j=1; j<=n; ++j)
			a[j]=f[i-1][j-1]+1;
		for(int j=1; j<=n; ++j)
			if(lasb[j])
				a[lasb[j]]=max(a[lasb[j]],a[j]+1);
		for(int j=1; j<=n; ++j)
			a[j]=max(a[j],a[j-1]);
		for(int j=1; j<=n; ++j)
			f[i][j]=max(f[i][j],a[j]);	
	}
	for(int i=1; i<=k; ++i)
	{
		for(int j=1; j<=n; ++j)
			cout<<f[i][j]<<' ';
		cout<<endl;
	}
	return f[k][n];
}
int p[N<<1],x[N];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>k;
	int pn=0;
	for(int i=1; i<=n; ++i)
	{
		scanf("%d",&p[i]),p[n+i]=p[i];
		if(p[i]==n)
			pn=i;
	}
	for(int i=pn+1,cnt=1; cnt<=n; ++cnt,++i)
		x[cnt]=p[i];
	int ans=work(x);
	for(int i=pn+n-1,cnt=1; cnt<=n; ++cnt,--i)
		x[cnt]=p[i];
	printf("%d\n",max(ans,work(x)));		
    return 0;
}