#include <bits/stdc++.h>
using namespace std;
class convex_hull {
private:
vector<long long> a, b;
vector<int> id;
int ptr = 0;
int bad(int l1, int l2, long long _a, long long _b) {
if ((a[l1] == _a) && (b[l1] == _b)) return 1;
return ((_b - b[l1]) * (a[l1] - a[l2]) > (b[l2] - b[l1]) * (a[l1] - _a));
}
public:
void add(long long _a, long long _b, int _id) {
while ((int) a.size() >= 2 && bad((int) a.size() - 1, (int) a.size() - 2, _a, _b)) {
a.pop_back();
b.pop_back();
id.pop_back();
}
a.push_back(_a);
b.push_back(_b);
id.push_back(_id);
}
pair<int, long long> query(long long x) {
if (ptr >= (int) a.size()) {
ptr = (int) a.size() - 1;
}
while (ptr < (int) a.size() - 1 && a[ptr + 1] * x + b[ptr + 1] >= a[ptr] * x + b[ptr]) {
ptr++;
}
return {id[ptr], a[ptr] * x + b[ptr]};
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<long long> pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
long long a;
cin >> a;
pre[i] = pre[i - 1] + a;
}
vector< vector<long long> > dp(2, vector<long long>(n + 1, 0));
vector< vector<int> > from(k + 1, vector<int>(n + 1, -1));
for (int t = 1; t <= k; t++) {
convex_hull v;
int cur = t % 2;
for (int i = 1; i <= n; i++) {
if (i > 1) {
auto tmp = v.query(pre[i]);
from[t][i] = tmp.first;
dp[cur][i] = tmp.second;
}
v.add(pre[i], dp[!cur][i] - pre[i] * pre[i], i);
}
}
cout << dp[k % 2][n] << '\n';
int cur = from[k][n], cnt = 1;
vector<int> ans;
while (cur != -1) {
ans.push_back(cur);
cur = from[k - cnt++][cur];
}
reverse(ans.begin(), ans.end());
for (auto& x : ans) {
cout << x << ' ';
}
cout << '\n';
return 0;
}
