#include <bits/stdc++.h>
using namespace std;
class bag {
private:
class line {
public:
long long m, b;
int j;
line(long long mm, long long bb, int id) {
m = mm;
b = bb;
j = id;
}
long double taq(const line& d) const {
return (long double) (d.b - b) / (long double) (m - d.m);
}
};
int I;
vector<pair<line, long double>> stk;
public:
bag() {
I = 0;
}
void insert_line(long long b, long long m, long long id) {
line d(m, b, id);
while (stk.size() > 1 && ((stk.back().first.m == m && stk.back().first.b <= b) || stk.back().second <= d.taq(stk.back().first))) {
stk.pop_back();
}
if (!stk.empty() && stk.back().first.m == m) {
if (stk.back().first.b > d.b) {
d = stk.back().first;
}
stk.pop_back();
}
stk.push_back({d, (stk.empty() ? LLONG_MAX : d.taq(stk.back().first))});
}
pair<long long, int> eval(long long x) {
I = min(I, (int) stk.size() - 1);
while (I < (int) stk.size() && (long double) x < stk[I].second) {
I++;
}
if (I >= (int) stk.size()) {
I = stk.size() - 1;
}
if (x >= stk[I].second) {
I--;
}
line d = stk[I].first;
return pair<long long, int>(d.m * x + d.b, d.j);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<long long> sum(n);
sum[0] = a[0];
for (int i = 1; i < n; i++) {
sum[i] = a[i] + sum[i - 1];
}
vector<long long> sr(n);
sr[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--) {
sr[i] = a[i] + sr[i + 1];
}
vector<long long> dp(n);
vector<vector<int>> en(k + 1, vector<int>(n, -1));
for (int i = 0; i < n; i++) {
dp[i] = (sum[n - 1] - sum[i]) * (sum[i]);
}
for (int i = 2; i <= k; i++) {
vector<long long> new_dp(n, 0);
bag chL;
chL.insert_line(dp[i - 2], sr[i - 1], i - 2);
for (int j = i - 1; j + 1 < n; j++) {
pair<long long, int> fromCh = chL.eval(sr[j + 1]);
new_dp[j] = fromCh.first - sr[j + 1] * sr[j + 1];
en[i][j] = fromCh.second;
chL.insert_line(dp[j], sr[j + 1], j);
}
swap(dp, new_dp);
}
pair<long long, int> p = {-1, -1};
for (int i = 0; i + 1 < n; i++) {
p = max(p, {dp[i], i});
}
cout << p.first << '\n';
int ptr = p.second;
for (int i = k; i > 0; i--) {
cout << ptr + 1 << " ";
assert(en[i][ptr] < ptr);
ptr = en[i][ptr];
}
cout << '\n';
return 0;
}
