#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(v) (int)v.size()
const int MAXN = 1e5+5;
const ll INF = 1e14;
int a[MAXN];
ll dp[2][MAXN], val[MAXN*4], add[MAXN*4], lz[MAXN*4];
void refresh(int node, int l, int r){
if(lz[node] == 0)return;
add[node] = lz[node];
if(l != r){
lz[node*2] = lz[node];
lz[node*2+1] = lz[node];
}
lz[node] = 0;
}
void update(int node, int l, int r, int i, int j, int t, ll x){
refresh(node,l,r);
if(j < l || r < i)return;
if(i <= l && r <= j){
if(t == 0){
lz[node] = x;
refresh(node,l,r);
}else val[node] = x;
return;
}
int mid = (l+r)/2, e = node*2, d = node*2+1;
update(e,l,mid,i,j,t,x); update(d,mid+1,r,i,j,t,x);
if(val[e] + add[e] < val[d] + add[d]){
val[node] = val[e]; add[node] = add[e];
}else{
val[node] = val[d]; add[node] = add[d];
}
}
ll query(int node, int l, int r, int i, int j){
refresh(node,l,r);
if(j < l || r < i)return INF;
if(i <= l && r <= j)return val[node]+add[node];
int mid = (l+r)/2, e = node*2, d = node*2+1;
return min( query(e,l,mid,i,j), query(d,mid+1,r,i,j) );
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,K; cin>>n>>K;
for(int i = 1; i <= n; i++)cin>>a[i];
for(int i = 1; i <= n; i++)dp[0][i] = INF; dp[0][n+1] = 0;
for(int k = 1; k <= K; k++){
vector<int> st;
dp[k&1][n+1] = INF;
for(int i = n; i >= 1; i--){
int r = i;
while(sz(st) > 0 && a[st.back()] < a[i]){
st.pop_back();
if(sz(st) > 0)r = st.back()+1;
else r = n;
}
update(1,1,n, i,r, 0, a[i]);
st.push_back(i);
update(1,1,n, i,i, 1, dp[(k-1)&1][i+1]);
dp[k&1][i] = query(1,1,n, i,n);
}
}
cout<<dp[K&1][1]<<"\n";
}
