#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FOR(I, L, R) for(int I(L); I <= (int)R ; ++I)
#define FOD(I, R, L) for(int I(R); I >= (int)L ; --I)
#define FOA(I, A) for(auto &I : A)
#define print(A, L, R) FOR(I, L, R){cout << A[I] <<' ';} cout << '\n';
#define printz(A, L, R) FOR(I, 0, L){FOR(J, 0, R){cout << A[I][J] << ' ';} cout << '\n';} cout << '\n';
#define prints(A) FOA(I, A) cout << I <<' '; cout << '\n';
#define fs first
#define sd second
#define ii pair<int, int>
#define iii pair<int, ii>
#define all(A) A.begin(), A.end()
#define quickly cin.tie(0) -> ios_base::sync_with_stdio(0);
#define FILE "dincpath"
const int N = 1e5 + 5;
const int K = 101;
const int mod = 1e9 + 7;
const int oo = 1e9;
struct Modint{
int x;
Modint(){x = 0;}
Modint(int _x){x = (_x + mod) % mod;}
Modint operator + (const Modint &other) const{ return Modint((x + other.x) % mod); }
Modint operator - (const Modint &other) const{ return Modint((x - other.x + mod) % mod); }
Modint operator * (const Modint &other) const{ return Modint((1LL * x * other.x) % mod); }
void operator += (const Modint &other) { *this = *this + other; }
void operator -= (const Modint &other) { *this = *this - other; }
void operator *= (const Modint &other) { *this = *this * other; }
friend ostream& operator << (ostream& os, const Modint &other){
return os << other.x;
}
};
int n, k;
int a[N], in[N];
stack<int> st;
struct node{
int cost, res, mx;
node(){cost = res = oo; mx = 0;}
node operator + (const node &other) const {
node _new;
_new.res = min(res, other.res);
_new.cost = min(cost, other.cost);
_new.mx = max(mx, other.mx);
return _new;
}
void change(int x){
mx = x;
res = cost + x;
}
};
struct SegmentTree{
node sg[N << 2];
int lazy[N << 2];
void push_down(int id, int l, int r){
if(lazy[id]){
int &x = lazy[id];
lazy[id << 1] = x;
lazy[id << 1 | 1] = x;
sg[id << 1].change(x);
sg[id << 1 | 1].change(x);
x = 0;
}
}
void updateCost(int id, int l, int r, int pos, int val){
if(l > pos || r < pos){
return;
}
if(l == r){
sg[id].cost = val;
sg[id].res = sg[id].mx + val;
return;
}
push_down(id, l, r);
int mid = (l + r) >> 1;
updateCost(id << 1, l, mid, pos, val);
updateCost(id << 1 | 1, mid + 1, r, pos, val);
sg[id] = sg[id << 1] + sg[id << 1 | 1];
}
void update(int id, int l, int r, int u, int v, int val){
if(l > v || r < u){
return;
}
if(u <= l && r <= v){
lazy[id] = val;
sg[id].change(val);
return;
}
push_down(id, l, r);
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
sg[id] = sg[id << 1] + sg[id << 1 | 1];
}
int get(int id, int l, int r, int pos){
if(l > pos || r < pos){
return oo;
}
if(l == r){
return sg[id].res;
}
push_down(id, l, r);
int mid = (l + r) >> 1;
return min(get(id << 1, l, mid, pos), get(id << 1 | 1, mid + 1, r, pos));
}
} sg[K];
signed main(){ quickly
if(fopen(FILE".inp", "r")){
freopen(FILE".inp", "r", stdin);
freopen(FILE".out", "w", stdout);
}
cin >> n >> k;
FOR(i, 1, n){
cin >> a[i];
}
a[0] = oo;
st.push(0);
FOR(i, 1, n){
while(a[st.top()] < a[i]){
st.pop();
}
in[i] = st.top();
st.push(i);
}
sg[0].updateCost(1, 0, n, 0, 0);
sg[0].update(1, 0, n, 0, 0, 0);
FOR(i, 1, n){
FOD(j, k, 1){
sg[j - 1].update(1, 0, n, in[i], i - 1, a[i]);
int val = sg[j - 1].sg[1].res;
sg[j].updateCost(1, 0, n, i, val);
}
}
cout << sg[k].get(1, 0, n, n);
}
