#include<bits/stdc++.h>
using namespace std;
const long long N = 1000*100+5;
const long long INF = 1000000000000000000;
struct line{
long long k,b;
line():k(0),b(0){}
line(long long _k,long long _b):k(_k),b(_b){}
};
struct node{
node* l;
node* r;
line ln;
node():l(NULL),r(NULL){}
};
long long f(line a, long long x) {
if(a.k == 0 && a.b == 0) return INF;
return (a.k*x+a.b);
}
const long long maxn = 1000000000;
long long n;
void add_line(line nw, node* v, long long l = 0, long long r = maxn) {
long long m = (l + r) / 2;
bool lef = f(nw, l) < f(v->ln, l);
bool mid = f(nw, m) < f(v->ln, m);
if(mid) {
swap(v->ln, nw);
}
if(r - l == 1) return;
else if(lef != mid) {
if(v->l == NULL) v->l = new node();
add_line(nw, v->l, l, m);
} else {
if(v->r == NULL) v->r = new node();
add_line(nw, v->r, m, r);
}
}
long long get(long long x, node* v, long long l = 0, long long r = maxn) {
long long m = (l + r) / 2;
if(r - l == 1) {
if(v == NULL) v = new node();
return f(v->ln, x);
}
else if(x < m) {
if(v->l == NULL) v->l = new node();
return min(f(v->ln, x), get(x, v->l, l, m));
}
else {
if(v->r == NULL) v->r = new node();
return min(f(v->ln, x), get(x, v->r, m, r));
}
}
long long dp[N][205];
long long a[N];
long long pref[N];
long long get(long long l,long long r){
return pref[r]-pref[l-1];
}
long long prevv[N][205];
int main()
{
ios_base::sync_with_stdio(false);
long long n,k;
cin>>n>>k;
for(long long i = 1;i<=n;i++) cin>>a[i];
for(long long i = 1;i<=n;i++) pref[i] = pref[i-1]+a[i];
long long ps = 0;
for(long long kk = 1;kk<=k;kk++){
for(long long i = 1;i<=n;i++){
for(long long j = 0;j<i;j++){
long long u = dp[j][kk-1]+get(j+1,i)*get(i+1,n);
if(u>=dp[i][kk]){
dp[i][kk] = u;
prevv[i][kk] = j;
if(kk == k && (u>dp[ps][kk] || ps == 0)){
ps = i;
}
}
}
}
// cout<<dp[kk][kk]<<endl;
}
cout<<dp[ps][k]<<endl;
cout<<ps<<endl;
long long kkk = k;
long long i = ps;
while(1){
i = prevv[i][kkk];
if(i == 0 || kkk == 1) break;
cout<<i<<endl;
kkk--;
}
return 0;
}
