#include <bits/stdc++.h>
#define DIM 100010
#define DIMK 210
using namespace std;
struct dreapta{
long long a,b;
} w[DIM];
int v[DIM],fth[DIM][DIMK],d[DIM];
long long dp[DIM][DIMK],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) * (b.a - a.a) < (a.b - b.b) * (c.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]);
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][j-1] - sp[i-1] * sp[n];
w[i-1].a *= -1, w[i-1].b *= -1; /// acum o sa caut minimul
while (u > 1 && intersectie(w[i-1],w[d[u]],w[d[u-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][j] = sp[i] * sp[n] - sp[i] * sp[i] + f (w[d[p]].a,w[d[p]].b,sp[i]) * (-1);
fth[i][j] = d[p];
}
}
int x, y = k;
long long maxi = 0;
for (i=1;i<=n;i++)
if (dp[i][k] > maxi)
maxi = dp[i][k], 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;
}
