#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int NM = 1e5, KM = 200;
int n, k, a[NM+5], pref[NM+5];
ll dp[2][NM+5];
int trace[KM+5][NM+5];
vector <int> arr;
void dnc(int t, int l, int r, int optl, int optr){
if (l > r) return;
int mid = (l+r)/2, opt = optl;
dp[t&1][mid] = dp[!(t&1)][opt]+1LL*pref[opt]*(pref[mid]-pref[opt]);
for (int i = opt+1; i <= min(optr, mid-1); i++){
ll tmp = dp[!(t&1)][i]+1LL*pref[i]*(pref[mid]-pref[i]);
if (tmp > dp[t][mid]){
dp[t&1][mid] = tmp;
opt = i;
}
}
trace[t][mid] = opt;
dnc(t, l, mid-1, optl, opt);
dnc(t, mid+1, r, opt, optr);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++){
cin >> a[i];
pref[i] = pref[i-1]+a[i];
}
for (int i = 2; i <= k+1; i++){
dnc(i, i, n, i-1, n-1);
}
cout << dp[(k+1)&1][n] << '\n';
int j = n;
for (int i = k+1; i > 1; i--){
arr.push_back(trace[i][j]);
j = trace[i][j];
}
reverse(arr.begin(), arr.end());
for (int x : arr) cout << x << ' ';
return 0;
}
