#include <bits/stdc++.h>
#define DIM 100001
#define DIMK 201
#define INF 2000000000
using namespace std;
struct dreapta{
long long a,b;
} w[DIM];
int v[DIM],fth[DIM][DIMK],d[DIM];
long long dp[DIM][2],sp[DIM];
vector <int> sol;
int n,k,i,j,p,u;
/*int intersectie (dreapta c, dreapta b, dreapta a){
return (a.b - c.b) * (a.a - b.a) < (b.b - a.b) * (c.a - a.a);
}*/
long double intersectie (dreapta a, dreapta b){
if (a.a == b.a)
return INF;
return 1.0 * (a.b - b.b) / (b.a - a.a);
}
long long f (long long a, long long b, long long x){
return a*x + b;
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>k;
for (i=1;i<=n;i++){
cin>>v[i];
sp[i] = sp[i-1] + v[i];
}
for (i=1;i<n;i++)
dp[i][1] = sp[i] * (sp[n] - sp[i]);
int t = 0;
for (j=2;j<=k;j++){
p = 1, u = 0;
for (i=j;i<=n;i++){
w[i-1].a = sp[i-1], w[i-1].b = dp[i-1][1-t] - sp[i-1] * sp[n];
while (u > p && intersectie(w[d[u]],w[d[u-1]]) > intersectie(w[d[u-1]],w[i-1]))
u--;
d[++u] = i-1;
while (p < u && f (w[d[p]].a,w[d[p]].b,sp[i]) <= f (w[d[p+1]].a,w[d[p+1]].b,sp[i]))
p++;
dp[i][t] = sp[i] * sp[n] - sp[i] * sp[i] + f (w[d[p]].a,w[d[p]].b,sp[i]);
fth[i][j] = d[p];
}
t = 1-t;
}
int x, y = k;
long long maxi = -1;
for (i=1;i<=n;i++)
if (dp[i][1-t] > maxi)
maxi = dp[i][1-t], x = i;
cout<<maxi<<"\n";
sol.push_back(x);
while (x){
sol.push_back(fth[x][y]);
x = fth[x][y];
y--;
}
for (i=sol.size()-2;i>=0;i--)
cout<<sol[i]<<" ";
return 0;
}
