#include <bits/stdc++.h>
using namespace std;
const long long is_query = -(1LL<<62);
struct line {
long long m, b;
int id;
mutable function<const line*()> succ;
bool operator<(const line& rhs) const {
if (rhs.b != is_query) return m < rhs.m;
const line* s = succ();
if (!s) return 0;
long long x = rhs.m;
return b - s->b < (s->m - m) * x;
}
};
struct dynamic_hull : public multiset<line> {
const long long inf = LLONG_MAX;
bool bad(iterator y) {
auto z = next(y);
if (y == begin()) {
if (z == end()) return 0;
return y->m == z->m && y->b <= z->b;
}
auto x = prev(y);
if (z == end()) return y->m == x->m && y->b <= x->b;
long long v1 = (x->b - y->b);
if (y->m == x->m) v1 = x->b > y->b ? inf : -inf;
else v1 /= (y->m - x->m);
long long v2 = (y->b - z->b);
if (z->m == y->m) v2 = y->b > z->b ? inf : -inf;
else v2 /= (z->m - y->m);
return v1 >= v2;
}
void insert_line(long long b, long long m, int id) {
auto y = insert({ m, b, id });
y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
if (bad(y)) { erase(y); return; }
while (next(y) != end() && bad(next(y))) erase(next(y));
while (y != begin() && bad(prev(y))) erase(prev(y));
}
pair<long long, int> eval(long long x) {
auto l = *lower_bound((line) { x, is_query });
return pair<long long, int>(l.m * x + l.b, l.id);
}
};
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);
dynamic_hull 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;
}
