#include <stdio.h>
#include <algorithm>
#include <vector>
#define M 100004
#define INF 1234567890
using namespace std;
int n, k;
struct pp{
long long int a, b;
int pos;
};
vector<pp> v;
long long int d[2][M], ans, s[M];
int path[209][M],pri[M];
int main(){
int i, j;
pp e;
scanf("%d %d", &n, &k);
for (i = 1; i <= n; i++) scanf("%lld", &s[i]);
for (i = 1; i <= n; i++) s[i] = s[i - 1] + s[i];
for (i = 1; i <= k; i++){
v.clear();
for (j = i - 1; j <= n; j++){
e.a = s[j]; e.b = d[0][j] - (long long)s[j] * s[j]; e.pos = j;
while (v.size() > 1){
int EE = v.size() - 1;
if ((v[EE].a - v[EE-1].a)*(e.b - v[EE].b) >= (e.a-v[EE].a)*(v[EE].b-v[EE-1].b)) v.pop_back();
else break;
}
v.push_back(e);
}
e.a = 0; e.b = -INF; e.pos = 0; v.push_back(e);
int pivot = 0;
for (j = i; j <= n; j++){
while (s[j] * v[pivot].a + v[pivot].b <= s[j] * v[pivot+1].a + v[pivot+1].b && v[pivot+1].pos < j) pivot++;
d[1][j] = s[j] * v[pivot].a + v[pivot].b;
path[i][j] = v[pivot].pos;
}
for (j = i; j <= n; j++) d[0][j] = d[1][j];
}
printf("%lld\n", d[1][n]);
int temp = path[k][n];
for (i = k; i >= 1; i--){
pri[i] = temp;
temp = path[i - 1][temp];
}
for (i = 1; i <= k; i++) printf("%d ", pri[i]);
}
