#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define evaluate(pt, x) (pt.first.first * x + pt.first.second)
const int N = 1e5, K = 201;
int a[N], p[K], n, k, last[N][K];
ll s[N], dp[N], dp_prev[N];
vector<pair<pair<ll, ll>, int>> hull;
ll find(int i, int j, ll x) {
for (; p[j] < (int)hull.size() - 1; p[j]++) {
if (evaluate(hull[p[j]], x) > evaluate(hull[p[j] + 1], x))
break;
}
last[i][j + 1] = hull[p[j]].second;
return evaluate(hull[p[j]], x);
}
bool inter(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {
return (a.second - b.second) * (c.first - a.first) > (a.second - c.second) * (b.first - a.first);
}
void insert(int j, pair<pair<ll, ll>, int> nl) {
while (hull.size() > 1) {
auto temp = hull.back();
hull.pop_back();
if (inter(nl.first, temp.first, hull.back().first)) {
hull.push_back(temp);
break;
}
p[j] = min(p[j], (int)hull.size() - 1);
}
hull.push_back(nl);
}
int solveTestCase() {
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
s[0] = a[0];
for (int i = 1; i < n; i++) s[i] = s[i - 1] + a[i];
/*for (int i = 1; i < n; i++) {
for (int j = 1; j <= k && j <= i; j++) {
dp[i][j] = find(i, j - 1, s[i]);
insert(j - 1, {{s[i], dp[i][j - 1] - s[i] * s[i]}, i});
}
insert(min(i, k), {{s[i], dp[i][min(i, k)] - s[i] * s[i]}, i});
}*/
for (int j = 1; j <= k; j++) {
insert(j - 1, {{s[j - 1], dp_prev[j - 1] - s[j - 1] * s[j - 1]}, j - 1});
for (int i = j; i < n; i++) {
dp[i] = find(i, j - 1, s[i]);
insert(j - 1, {{s[i], dp_prev[i] - s[i] * s[i]}, i});
dp_prev[i] = dp[i];
}
hull.clear();
}
cout << dp[n - 1] << "\n";
for (int i = last[n - 1][k], j = k; j > 0; --j, i = last[i][j]) cout << i + 1 << " ";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test = 1;
// cin >> test;
while (test--)
solveTestCase();
}
