#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define N 110005
using namespace std;
typedef long long ll;
typedef pair < ll , ll > ii;
ll n, k, bas, son, a[N], pre[N], dp[N][205], git[N][205];
pair < ll , ii > q[N];
inline long double kesisim(ii a, ii b){return 1.0 * ( b.nd - a.nd ) / (1.0 * (a.st - b.st) + 0.000000000001) ;}
void ekle(ll i, ii d){
// if(d == mp(0ll, 0ll))
// return;
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);
}
ll bul(ll 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("%lld %lld",&n ,&k);
for(ll i = 1; i <= n; i++){
scanf("%lld",a + i);
pre[i] = pre[i - 1] + a[i];
}
for(ll x = 1; x <= k; x++){
bas = 1, son = 0;
ekle(0, mp(0, 0));
for(ll i = 1; i <= n; i++){
ll 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(ll j = 1; j < i; j++){
// if(dp[j][x - 1] + pre[j]*pre[i] - pre[j]*pre[j] >= dp[i][x]){
// dp[i][x] = dp[j][x - 1] + pre[j]*pre[i] - pre[j]*pre[j];
// git[i][x] = j;
// }
// // dp[i][x] = max(dp[i][x], dp[j][x - 1] + pre[j]*pre[i] - pre[j]*pre[j]);
// }
// printf("dp[%lld][%lld] = %lld %lld\n", i, x, dp[i][x], j);
// if(a[i] != 0)
ekle(i, mp(pre[i], dp[i][x - 1] - pre[i]*pre[i]) );
// cout << i << " -> " << pre[i] << " " << dp[i][x - 1] - pre[i]*pre[i] << " eklendi" << endl;
}
}
printf("%lld\n", dp[n][k]);
son = n;
bas = k;
// if(dp[n][k] == 0){
// for(int i = 1; i <= k; i++)
// printf("%d ", i);
// return 0;
// }
for(ll i = 1; i <= k; i++){
printf("%lld ", git[son][bas]);
son = git[son][bas];
bas--;
}
return 0;
}
