#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000000
#define inf 1000000000000000000ll
#define N 100005
#define LOG 20
#define magic 100
#define KOK 250
#define EPS 0.0025
#define pw(x) (1<<(x))
#define PI 3.1415926535
#define loloi pair<lolo, int>
using namespace std;
int n, k, x, ptr;
ll dp[2][N], pre[N];
int tut[201][100001];
vector <loloi> v;
ll res(lolo line, ll x){
return line.st * x + line.nd;
}
ll get(ll val){
while (ptr + 1 < sz(v) &&
res(v[ptr].st, val) < res(v[ptr + 1].st, val)){
ptr++;
}
return res(v[ptr].st, val);
}
lf inter(lolo line1, lolo line2){
return 1.0 * (line2.nd - line1.nd) / (line1.st - line2.st);
}
void up(ll a, ll b, int ind){
while (sz(v) > 1 &&
inter({a,b}, v[sz(v) - 1].st) <= inter({a, b}, v[sz(v) - 2].st)){
v.ppb();
}
v.pb({{a, b}, ind});
ptr = min(ptr, sz(v) - 1);
}
void clear(){
ptr = 0;
v.clear();
}
int main(){
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++){
scanf("%d", &x);
pre[i] = pre[i - 1] + x;
}
for (int i = 1; i <= k; i++){
clear();
up(pre[i], -pre[i] * pre[i] + dp[0][i], i);
for (int j = i + 1; j <= n; j++){
dp[1][j] = get(pre[j]);
tut[i][j] = v[ptr].nd;
up(pre[j], -pre[j] * pre[j] + dp[0][j], j);
dp[0][j] = dp[1][j];
}
}
printf("%lld\n", dp[0][n]);
for (int i = tut[k][n]; i >= 1; i = tut[k][i]){
k--;
printf("%d ", i);
}
assert(k == 0);
}
