#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1e5+5, Log=17, pot=(1<<Log), maxk=105;
const int inf=1e9;
struct tournament{
int t[pot*2];
int mindp[pot*2];
int prop[pot*2];
tournament(){
for(int i=0; i<pot*2; i++){
t[i]=inf;
mindp[i]=inf;
}
}
void propagate(int x){
if(!prop[x]){
return;
}
t[x]=prop[x]+mindp[x];
if(x<pot){
prop[x*2]=prop[x];
prop[x*2+1]=prop[x];
}
prop[x]=0;
}
void update0(int x, int val){
mindp[x]=val;
for(x/=2; x>0; x/=2){
mindp[x]=min(mindp[x*2], mindp[x*2+1]);
}
}
void update(int x, int val){
t[x]=mindp[x]+val;
for(x/=2; x>0; x/=2){
propagate(x*2);
propagate(x*2+1);
t[x]=min(t[x*2], t[x*2+1]);
}
}
void update2(int L, int D, int x, int l, int d, int val){
propagate(x);
if(L>=l && D<=d){
update(x, val);
if(x<pot){
prop[x*2]=val;
prop[x*2+1]=val;
}
return;
}
if((L+D)/2>=l){
update2(L, (L+D)/2, x*2, l, d, val);
}
if((L+D)/2+1<=d){
update2((L+D)/2+1, D, x*2+1, l, d, val);
}
}
int query(int L, int D, int x, int l, int d){
propagate(x);
if(L>=l && D<=d){
return t[x];
}
int lijeva=1e9, desna=1e9;
if((L+D)/2>=l){
lijeva=query(L, (L+D)/2, x*2, l, d);
}
if((L+D)/2+1<=d){
desna=query((L+D)/2+1, D, x*2+1, l, d);
}
return min(lijeva, desna);
}
};
struct logaritamska{
int l[maxn];
void update(int x, int val){
for(; x<maxn; x+=(x & -x)){
l[x]=max(l[x], val);
}
}
int query(int x){
int sol=0;
for(; x>0; x-=(x & -x)){
sol=max(sol, l[x]);
}
return sol;
}
};
tournament T[maxk];
logaritamska L;
int n, k;
int rijesi(int x, int pos){
int rev=maxn-pos;
int lo=rev, hi=maxn-1, mid;
while(lo<hi){
mid=(lo+hi)/2+1;
if(L.query(mid)<x){
lo=mid;
}
else{
hi=mid-1;
}
}
L.update(rev, x);
return maxn-lo;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
int a;
int pos;
int maksi=0;
for(int i=0; i<n; i++){
cin >> a;
maksi=max(maksi, a);
pos=rijesi(a, i+1)-1;
// cout << pos << endl;
T[1].update0(i+1+pot, maksi);
for(int j=2; j<=k; j++){
if(j>i+1){
break;
}
else{
// cout << "uso " << i << ' ' << j << endl;
T[j-1].update2(0, pot-1, 1, pos, i, a);
// cout << T[j-1].query(0, pot-1, 1, pos, i) << endl;
T[j].update0(i+pot+1, T[j-1].t[1]);
}
}
}
if(k==1){
cout << maksi << '\n';
}
else{
cout << T[k].mindp[n+pot] << '\n';
}
}
