const long long INF = LLONG_MAX/4;
// segment tree hỗ trợ range‐add & range‐min
struct SegTree {
int n;
vector<long long> st, lazy;
SegTree(int _n): n(_n), st(4*n, INF), lazy(4*n, 0) {}
void apply(int p, int l, int r, long long v) {
st[p] += v;
lazy[p] += v;
}
void push(int p, int l, int r) {
if (lazy[p]!=0) {
int m=(l+r)/2;
apply(p<<1, l, m, lazy[p]);
apply(p<<1|1, m+1, r, lazy[p]);
lazy[p]=0;
}
}
void pull(int p) {
st[p] = min(st[p<<1], st[p<<1|1]);
}
void build(int p, int l, int r, vector<long long>& base) {
if (l==r) {
st[p] = base[l];
return;
}
int m=(l+r)/2;
build(p<<1, l, m, base);
build(p<<1|1, m+1, r, base);
pull(p);
}
void range_add(int p, int l, int r, int i, int j, long long v) {
if (i>r||j<l) return;
if (i<=l&&r<=j) {
apply(p,l,r,v);
return;
}
push(p,l,r);
int m=(l+r)/2;
range_add(p<<1, l, m, i, j, v);
range_add(p<<1|1, m+1, r, i, j, v);
pull(p);
}
long long range_min(int p, int l, int r, int i, int j) {
if (i>r||j<l) return INF;
if (i<=l&&r<=j) return st[p];
push(p,l,r);
int m=(l+r)/2;
return min(
range_min(p<<1, l, m, i, j),
range_min(p<<1|1, m+1, r, i, j)
);
}
};
// Trong phần main hoặc hàm tính DP cho từng k:
vector<long long> dp_prev(n+1), dp_cur(n+1);
dp_prev[0] = 0;
for(int i=1;i<=n;i++) dp_prev[i]=INF;
for(int k=1;k<=K;k++){
// 1) khởi base = dp_prev
SegTree st(n+1);
st.build(1, 0, n, dp_prev);
// 2) monotonic stack để track các interval
vector<int> stk;
// Mảng để lưu biên trái của mỗi phần tử trong stack
vector<int> left(n+1);
stk.reserve(n);
for(int i=1;i<=n;i++){
int L = i;
// pop các a[stk.top] <= a[i]
while(!stk.empty() && a[stk.back()] <= a[i]){
int t = stk.back(); stk.pop_back();
int lt = left[t];
// với mọi j trong [lt-1, t-1], max cũ = a[t] -> cập nhật thành a[i]
st.range_add(1, 0, n, lt-1, t-1, a[i] - a[t]);
L = lt;
}
stk.push_back(i);
left[i] = L;
// bây giờ query dp_cur[i]
dp_cur[i] = st.range_min(1, 0, n, 0, i-1);
}
// đổi mảng
dp_prev = dp_cur;
fill(dp_cur.begin(), dp_cur.end(), INF);
}
// Kết quả: dp_prev[n]
cout << dp_prev[n] << "\n";
