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