#include <bits/stdc++.h>
using namespace std;
class sparse_table_min {
public:
sparse_table_min(vector<long long>&a) : n(a.size()) {
lg.resize(1 + n);
lg[0] = lg[1] = 0;
for (int i = 2; i <= n; i++)
lg[i] = lg[i / 2] + 1;
mn.assign(n, vector<long long>(1 + lg[n]));
for (int j = 0; j <= lg[n]; j++)
for (int i = 0; i <= n - (1 << j); i++)
if (j == 0) mn[i][j] = a[i];
else mn[i][j] = min(mn[i][j-1], mn[i+(1<<(j-1))][j-1]);
}
long long query(int l, int r) {
int d = lg[r-l+1];
return min(mn[l][d], mn[r-(1<<d)+1][d]);
}
private:
int n;
vector<int> lg;
vector<vector<long long>> mn;
};
class sparse_table_max {
public:
sparse_table_max(vector<long long>&a) : n(a.size()) {
lg.resize(1 + n);
lg[0] = lg[1] = 0;
for (int i = 2; i <= n; i++)
lg[i] = lg[i / 2] + 1;
mx.assign(n, vector<long long>(1 + lg[n]));
for (int j = 0; j <= lg[n]; j++)
for (int i = 0; i <= n - (1 << j); i++)
if (j == 0) mx[i][j] = a[i];
else mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
}
long long query(int l, int r) {
int d = lg[r-l+1];
return max(mx[l][d], mx[r-(1<<d)+1][d]);
}
private:
int n;
vector<int> lg;
vector<vector<long long>> mx;
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<long long> a(1 + n, 1e18);
vector<vector<long long>> dp(1 + k, vector<long long>(1 + n, 1e18));
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sparse_table_max mx(a);
for (int i = 1; i <= n; i++) {
dp[1][i] = mx.query(1, i);
}
sparse_table_min mn(dp[1]);
vector<int> left(n + 1, 0);
for (int i = 2; i <= n; i++) {
int l = 1, r = i;
while (l < r) {
int m = (l + r) / 2;
if (mx.query(m, i) == a[i])
r = m;
else
l = m + 1;
}
left[i] = r;
}
int K = k;
for (int k = 2; k <= K; k++) {
for (int i = 2; i <= n; i++) {
dp[k][i] = min(dp[k][i], dp[k][left[i] - 1]);
if (mx.query(left[i], i) == a[i]) {
dp[k][i] = min(dp[k][i], mn.query(left[i] - 1, i - 1) + a[i]);
}
}
mn = sparse_table_min(dp[k]);
}
cout << dp[k][n] << '\n';
return 0;
}
