#include <bits/stdc++.h>
#define X first
#define Y second
#define ll long long
#define MP make_pair
using namespace std;
const int N = 1e5 + 123;
const ll INF = 1e18;
typedef pair<ll, ll> Line;
ll f(Line me, ll x) {
return me.X * x + me.Y;
}
Line cf[N];
int n, k, his[N][202], CHT[N];
ll s[N], dp[N];
bool bad(int x, int y, int z) {
return (cf[x].Y - cf[y].Y) * 1.0 / (cf[y].X - cf[x].X) >= (cf[x].Y - cf[z].Y) * 1.0 / (cf[z].X - cf[x].X);
}
void solve(int st) {
CHT[1] = st - 1;
cf[st - 1] = {s[st - 1], dp[st - 1] - s[st - 1] * s[st - 1]};
for(int i = st, l = 1, r = 1;i <= n;i++) {
while(l < r && f(cf[CHT[l]], s[i]) <= f(cf[CHT[l + 1]], s[i]))
l++;
cf[i] = {s[i], dp[i] - s[i] * s[i]};
dp[i] = f(cf[CHT[l]], s[i]), his[i][st] = CHT[l];
while(l < r && bad(CHT[r - 1], CHT[r], i))
r--;
CHT[++r] = i;
}
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 1;i <= n;i++)
cin >> s[i], s[i] += s[i - 1];
k += 1;
for(int i = 2;i <= k;i++) {
solve(i);
}
cout << dp[n] << "\n";
int pos = n;
for(int i = k;i >= 2;i--) {
pos = his[pos][i];
cout << pos << " ";
}
}
