#include <bits/stdc++.h>
#define taskname "main"
#define debug(a, l, r) for (int _i = (l); _i <= (r); _i++) cout<<(a)[_i]<<' '; cout<<'\n';
using namespace std;
const int
maxN = 2e5,
oo = 2e9;
int n, k,
a[maxN + 1],
lim[maxN + 1],
dp[maxN + 1];
stack <int> mono_st;
struct SegTree
{
struct Node
{
int org, lazy, res;
} nodes[4 * maxN + 1];
void build(int id, int l, int r)
{
if (l == r)
{
nodes[id] = {dp[l - 1], -1, dp[l - 1]};
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
nodes[id] = {
min(nodes[id << 1].org, nodes[id << 1 | 1].org),
-1,
min(nodes[id << 1].res, nodes[id << 1 | 1].res)
};
}
void push(int id, int l, int r)
{
if (nodes[id].lazy == -1)
return;
nodes[id].res = nodes[id].org + nodes[id].lazy;
if (l != r)
{
nodes[id << 1].lazy = nodes[id].lazy;
nodes[id << 1 | 1].lazy = nodes[id].lazy;
}
nodes[id].lazy = -1;
}
void upd(int id, int l, int r, int u, int v, int val)
{
push(id, l, r);
if (v < l || r < u)
return;
if (u <= l && r <= v)
{
nodes[id].lazy = val;
push(id, l, r);
return;
}
int mid = (l + r) >> 1;
upd(id << 1, l, mid, u, v, val);
upd(id << 1 | 1, mid + 1, r, u, v, val);
nodes[id] = {
min(nodes[id << 1].org, nodes[id << 1 | 1].org),
-1,
min(nodes[id << 1].res, nodes[id << 1 | 1].res)
};
}
int get(int id, int l, int r, int u, int v)
{
push(id, l, r);
if (v < l || r < u)
return oo;
if (u <= l && r <= v)
return nodes[id].res;
int mid = (l + r) >> 1,
nl = get(id << 1, l, mid, u, v),
nr = get(id << 1 | 1, mid + 1, r, u, v);
return min(nl, nr);
}
} stree;
void init()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
a[0] = oo;
mono_st.push(0);
for (int i = 1; i <= n; i++)
{
while (a[mono_st.top()] < a[i])
mono_st.pop();
lim[i] = mono_st.top() + 1;
mono_st.push(i);
}
}
void solve()
{
for (int i = 1; i <= n; i++)
dp[i] = oo;
for (int t = 1; t <= k; t++)
{
stree.build(1, 1, n);
dp[0] = oo;
for (int i = 1; i <= n; i++)
{
stree.upd(1, 1, n, lim[i], i, a[i]);
dp[i] = stree.get(1, 1, n, 1, i);;
}
}
cout << dp[n];
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
init(); solve();
}
