#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const ll INF = 1e18;
const int N = 1e5 + 5, K = 205;
ll dp[2][N], a[N], p[N];
int anc[K][N];
struct Line {
ll k, b;
int pos;
bool q = false;
double lx;
bool operator < (const Line &oth) const {
if (q)
return k < oth.lx;
if (oth.q)
return lx < oth.k;
return k > oth.k;
}
};
struct CHT : vector<Line> {
bool bad(iterator y) {
iterator x, z;
if (y != begin()) {
x = prev(y);
if (x->k == y->k)
return x->b <= y->b;
}
if (next(y) != end()) {
z = next(y);
if (y->k == z->k)
return y->k > z->k;
}
if (y == begin() || next(y) == end())
return false;
return (x->b - y->b) * 1.0 * (z->k - y->k) >=
(y->b - z->b) * 1.0 * (y->k - x->k);
}
void calcLx(iterator y) {
if (y == begin()) {
y->lx = -INF;
}
else {
auto x = prev(y);
y->lx = (x->b - y->b) / (double)(y->k - x->k);
}
}
void add(Line a) {
push_back(a);
if (bad(prev(end()))) {
pop_back();
return;
}
while (size() > 1 && bad(end() - 2)) {
erase(end() - 2);
}
calcLx(prev(end()));
}
int que(ll x) {
auto it = upper_bound(begin(), end(), Line{x, -1, -1, 1});
it--;
return it->pos;
}
} cht;
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
p[i + 1] = a[i] + p[i];
}
k++;
for (int i = 1; i <= n; i++) {
dp[1][i] = p[i] * p[i];
}
for (int i = 2; i <= k; i++) {
cht.clear();
for (int j = i; j <= n; j++) {
cht.add({-2 * p[j - 1], dp[(i & 1) ^ 1][j - 1] + p[j - 1] * p[j - 1], j - 1});
int x = cht.que(p[j]);
dp[i & 1][j] = dp[(i & 1) ^ 1][x] + (p[j] - p[x]) * (p[j] - p[x]);
anc[i][j] = x;
}
}
cout << p[n] * (p[n] - 1) / 2 - (dp[k & 1][n] - p[n]) / 2 << "\n";
vector<int> v;
while (anc[k][n] > 0) {
n = anc[k][n];
v.push_back(n);
k--;
}
reverse(all(v));
for (int i : v)
cout << i << " ";
return 0;
}
