#include <bits/stdc++.h>
#include <windows.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int n,k;
int a[600005],b[600005],_pos[600005];
vector <int> sta;
vector <pii> Mx;
int f[600005],g[600005];
int fa[600005],_l[600005],_r[600005],val[600005],delta[600005];
int fnd(int u){
if(fa[u] == u) return u;
return fa[u] = fnd(fa[u]);
}
int mrg(int u,int v){
if(_r[u] - _l[u] > _r[v] - _l[v]){
swap(u,v);
swap(val[u],val[v]);
swap(delta[u],delta[v]);
}
fa[v] = u;
chkmin(_l[u],_l[v]);
chkmax(_r[u],_r[v]);
delta[u] += delta[v];
// cerr << "mrg " << u << " " << v << endl;
// Sleep(1000);
// cerr << val[u] << endl;
return u;
}
int answer,idx;
void push(int pos){
val[pos] = g[pos - 1] - (pos - 1);
// cerr << "PUSH " << pos << " " << val[pos] << endl;
int u = fnd(pos - 1);
while(val[u] + delta[u] <= val[pos]) u = mrg(fnd(_l[u] - 1),u);
if(!_l[u]){
answer = val[pos];
idx = pos;
}
}
void add(int pos,int lim){//pos 后缀加 1
// cerr << "add " << pos << " lim=" << lim << endl;
if(idx < pos) answer--;
pos--;//[1,pos] 减 1
int u = fnd(pos),nxt = fnd(_r[u] + 1);
delta[u]--;
if(nxt > lim) return;
while(val[u] + delta[u] <= val[nxt]){
if(idx == _l[u]){
answer += val[nxt] - val[u] - delta[u];
idx = _l[nxt];
}
u = mrg(fnd(_l[u] - 1),u);
}
}
void debug(int lim){
rep(i,1,lim) if(fa[i] == i) cerr << i << " l=" << _l[i] << " r=" << _r[i] << " val=" << val[i] << " delta=" << delta[i] << endl;
cerr << "answer=" << answer << " idx=" << idx << endl;
}
void trans(){
val[0] = inf;
sta.clear();Mx.clear();
rep(i,1,n){
int cur = -inf;
while(!sta.empty() && a[i] > a[sta.back()]){
chkmax(cur,Mx.back().first);
sta.pop_back();
Mx.pop_back();
}
chkmax(cur,g[i - 1]);
if(!Mx.empty()) Mx.eb(mkp(cur,max(Mx.back().second,cur - SZ(sta))));
else Mx.eb(mkp(cur,cur));
sta.eb(i);
f[i] = Mx.back().second + SZ(sta);
// printf("pos=%d\n",i);
// for(int p:sta) printf("%d ",p);
// printf("\n");
// for(pii I:Mx) printf("(%d,%d) ",I.first,I.second);
// printf("\n");
}
rep(i,0,n){
fa[i] = _l[i] = _r[i] = i;
delta[i] = 0;
}
answer = 0;
rep(i,1,n){
push(i);
add(_pos[i] + 1,i);
chkmax(f[i],answer + i);
// cerr << "result= " << answer << endl;
// debug(i);
}
rep(i,1,n) g[i] = f[i];
// rep(i,1,n) cerr << g[i] << " ";
// cerr << endl;
}
int solve(){
// rep(i,1,n) cerr << a[i] << " ";
// cerr << endl;
sta.clear();
g[0] = -inf;
rep(i,1,n){
while(!sta.empty() && a[i] > a[sta.back()]) sta.pop_back();
if(sta.empty()) _pos[i] = 0;
else _pos[i] = sta.back();
sta.eb(i);
g[i] = SZ(sta);
}
/* rep(i,1,n) printf("%d ",g[i]);
printf("\n");
printf("_pos:\n");
rep(i,1,n) printf("%d ",_pos[i]);
printf("\n");*/
rep(i,1,k - 1) trans();
int ans = 0;
rep(i,1,n) chkmax(ans,g[i]);
// printf("%d\n",ans);
return ans;
}
int main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
scanf("%d%d",&n,&k);
int pos = -1;
rep(i,1,n){
scanf("%d",&b[i]);
if(b[i] == n) pos = i;
}
assert(pos != -1);
rep(i,pos,n) a[i - pos + 1] = b[i];
rep(i,1,pos - 1) a[n - pos + 1 + i] = b[i];
int ans = solve();
reverse(a + 2,a + n + 1);
printf("%d\n",max(ans,solve()));
// printf("%d\n",ans);
return 0;
}