#include <bits/stdc++.h>
using namespace std;
#define F(i,l,r) for(int i=(l);i<=(r);i++)
#define D(i,l,r) for(int i=(l);i>=(r);i--)
const int N=1.2e6+5,inf=1e9,M=35;
struct tr{
    int fa[N];
    int f(int x){
        if(x==fa[x])return x;
        return fa[x]=f(fa[x]);
    }
    void hb(int a,int b){
        if(f(a)!=f(b))fa[f(b)]=f(a);
    }
}t1,t2;
struct node{
    int lst,nxt,laz;
}l1[N],l2[N];
int n,k,w[N],p[N],lst[N],nxt[N],res,f[M][N],f1[N],f2[N];
vector<int>st,g1[N],g2[N];
deque<int>qs;
void del(node*q,int x){
    if(q[x].laz)q[q[x].nxt].laz+=q[x].laz;
    q[q[x].lst].nxt=q[x].nxt;
    q[q[x].nxt].lst=q[x].lst;
}
void upt(node*q,int x,int*g,tr&t){
    while(q[x].lst&&g[q[x].lst]<=g[x]+q[x].laz)t.hb(x,q[x].lst),del(q,q[x].lst);
}
void Solve(){
    F(i,1,n)g1[i].clear(),g2[i].clear();
    qs.clear();
    for(int i=1;i<=n;i++)qs.push_back(w[i]);
    while(qs.front()!=n)qs.push_front(qs.back()),qs.pop_back();
    for(int i=1;i<=n;i++)p[i]=qs[i-1];
    p[0]=p[n+1]=inf;
    st.clear();
    st.push_back(0);
    F(i,1,n){
        while(p[st.back()]<p[i])st.pop_back();
        lst[i]=st.back();
        st.push_back(i);
    }
    st.clear();
    st.push_back(n+1);
    D(i,n,1){
        while(p[st.back()]<p[i])st.pop_back();
        nxt[i]=st.back();
        st.push_back(i);
    }
    F(i,1,n)g1[lst[i]].push_back(i),g2[nxt[i]].push_back(i);
    memset(f,-0x3f,sizeof(f));
    f[0][0]=0;
    F(t,1,k){
        memset(f1,0,sizeof(f1));
        memset(f2,0,sizeof(f2));
        F(i,1,n)t1.fa[i]=t2.fa[i]=i;
        int tg=0;
        l1[0].nxt=l2[0].nxt=1;
        F(i,1,n)l1[i]={i-1,i+1,0},l2[i]={i-1,i+1,0};
        F(i,1,n){
            f1[i]+=f[t-1][i-1]-i+1;
            f2[i]+=f[t-1][i-1]-i+1;
            upt(l1,i,f1,t1);
            l1[t1.f(lst[i]+1)].laz++;
            upt(l1,t1.f(lst[i]+1),f1,t1);
            for(auto u:g2[i]){
                l2[t2.f(u+1)].laz++;
                upt(l2,t2.f(u+1),f2,t2);
                tg--;
            }
            int x=l1[0].nxt,y=l2[0].nxt;
            f[t][i]=max(f1[x]+l1[x].laz,f2[y]+l2[y].laz+i+tg);
        }
    }
    F(i,1,n)res=max(res,f[k][i]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    #ifdef zzafanti
    freopen("in.txt","r",stdin);
    #endif
    #ifdef orz
    freopen("out.txt","w",stdout);
    #endif
    cin>>n>>k;
    F(i,1,n)cin>>w[i];
    Solve();
    reverse(w+1,w+n+1);
    Solve();
    cout<<res;
}