#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
int n, k, bas, son, a[N], pre[N], dp[N][205], git[N][205];
pair < int , ii > q[N];
inline double kesisim(ii a, ii b){return 1.0 * ( b.nd - a.nd ) / (a.st - b.st);}
void ekle(int i, ii d){
while(son - bas + 1 >= 2){
ii d1 = q[son].nd;
ii d2 = q[son - 1].nd;
if(kesisim(d, d2) <= kesisim(d1, d2))
son--;
else
break;
}
q[++son] = mp(i, d);
}
int bul(int x){
if(son - bas + 1 == 0)
return 0;
while(son - bas + 1 >= 2){
ii d1 = q[bas].nd;
ii d2 = q[bas + 1].nd;
if(kesisim(d1, d2) <= x)
bas++;
else
break;
}
return q[bas].st;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d %d",&n ,&k);
for(int i = 1; i <= n; i++){
scanf("%d",a + i);
pre[i] = pre[i - 1] + a[i];
}
for(int x = 1; x <= k; x++){
bas = 1, son = 0;
for(int i = 1; i <= n; i++){
int j = bul(pre[i]);
dp[i][x] = max(dp[i][x], dp[j][x - 1] + pre[j]*pre[i] - pre[j]*pre[j]);
git[i][x] = j;
// for(int j = 1; j < i; j++){
// dp[i][x] = bul();
// dp[i][x] = max(dp[i][x], dp[j][x - 1] + pre[j]*pre[i] - pre[j]*pre[j]);
// }
ekle(i, mp(pre[i], dp[i][x - 1] - pre[i]*pre[i]) );
// printf("dp[%d][%d] = %d\n", i, x, dp[i][x]);
}
}
printf("%d\n", dp[n][k]);
son = n;
bas = k;
for(int i = 1; i <= k; i++){
printf("%d ", git[son][bas]);
son = git[son][bas];
bas--;
}
return 0;
}
