#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = (int) 1e5 + 7;
const int K = (int) 2e2 + 7;
int a[N], sp[N], dp[N][K], rec[N][K];
struct Line {
int a;
int b;
int ind;
int eval(int x) {
return a * x + b;
}
};
struct Fraction {
int num;
ll den;
};
Fraction x(Line l1, Line l2) {
// l1.a * x + l1.b = y
// l2.a * x + l2.b = y
// l1.a * x + l1.b = l2.a * x + l2.b
// l1.a * x - l2.b * x = l2.b - l1.b
// (l1.a - l2.b) * x = l2.b - l1.b
// x = (l2.b - l1.b) / (l1.a - l2.a)
if (l1.a - l2.a > 0) {
return {l2.b - l1.a, l1.a - l2.a};
} else {
return {-(l2.b - l1.b), -(l1.a - l2.a)};
}
}
bool operator <= (const Fraction &a, const Fraction &b) {
return a.num * b.den <= a.den * b.num;
}
deque<Line> DS;
void add(Line line) {
while ((int) DS.size() >= 2 && x(DS.end()[-1], line) <= x(DS.end()[-2], DS.end()[-1])) {
DS.pop_back();
}
DS.push_back(line);
}
pair<ll, int> query(int x) {
while ((int) DS.size() >= 2 && DS[0].eval(x) <= DS[1].eval(x)) {
DS.pop_front();
}
return {DS[0].eval(x), DS[0].ind};
}
void solve(int layer, int n) {
DS.clear();
for (int i = layer; i <= n; i++) {
add({sp[i - 1], dp[layer - 1][i - 1] - sp[i - 1] * sp[i - 1], i - 1});
pair<int, int> aux = query(sp[i]);
dp[layer][i] = aux.first;
rec[layer][i] = aux.second;
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
sp[i] = sp[i - 1] + a[i];
dp[1][i] = 0;
}
for (int i = 2; i <= k + 1; i++) {
solve(i, n);
}
cout << dp[k + 1][n] << "\n";
vector<int> sol;
int aux = rec[k + 1][n];
while (k > 0) {
sol.push_back(aux);
aux = rec[k][aux];
k--;
}
reverse(sol.begin(), sol.end());
for (auto &it : sol) {
cout << it << " ";
}
return 0;
}
