#include <bits/stdc++.h>
using namespace std;
const int N = 300 * 1000 + 5, K = 205;
const long long inf = 1e18 + N;
int n, k;
int a[N];
long long dp[N][K];
long long ps[N];
int par[N][K];
vector <int> vec;
long long get(int lv, int x, int y) {
return 1ll * (ps[x] - ps[y]) * (ps[x] - ps[y]) + dp[y][lv - 1];
}
void solve(int lv, int l, int r, int s, int e) {
if (r <= l) {
return;
}
int md = (l + r) / 2;
for (int i = s; i <= e; i++) {
if (get(lv, md, i) < dp[md][lv]) {
par[md][lv] = i;
dp[md][lv] = get(lv, md, i);
}
}
solve(lv, l, md, s, par[md][lv]);
solve(lv, md + 1, r, par[md][lv], e);
}
int main() {
cin >> n >> k;
k++;
for (int i = 1; i <= n; i++) {
cin >> a[i];
ps[i] = ps[i - 1] + a[i];
for (int j = 0; j <= k; j++) {
dp[i][j] = inf;
}
}
for (int j = 1; j <= k; j++) {
solve(j, 1, n + 1, 0, n);
// for (int i = 1; i <= n; i++) {
// cout << "73 " << i << " " << j << " " << dp[i][j] << endl;
// }
}
cout << (1ll * ps[n] * ps[n] - dp[n][k]) / 2 << '\n';
int v = n;
for (int j = k; j > 0; j--) {
v = par[v][j];
if (v) {
vec.push_back(v);
}
}
sort(vec.begin(), vec.end());
for (auto x : vec) {
cout << x << " ";
}
return 0;
}
