#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> ii;
const int N = 1e5 + 5;
const int M = 205;
int a[N],lst,n,k,from[N][M];
ll pre[N],dp[N][2];
ll get(int l,int r) {
return pre[r] - pre[l - 1];
}
void f(int l,int r,int optl,int optr) {
if (l > r || optl > optr)
return;
int mid = (l + r) / 2;
int new_opt = mid;
for (int i = max(mid + 1,optl) ; i <= optr ; i++) {
if (dp[mid][0] < dp[i][1] + get(mid, i - 1) * get(i,n)) {
dp[mid][0] = dp[i][1] + get(mid,i - 1) * get(i,n);
new_opt = i;
}
}
from[mid][lst] = new_opt;
f(l,mid - 1,optl,new_opt);
f(mid + 1,r,new_opt,optr);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> k;
for (int i = 1 ; i <= n ; i++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
for (int i = 1 ; i <= k ; i++) {
lst = i;
for (int j = 1 ; j <= n ; j++) {
dp[j][1] = dp[j][0];
dp[j][0] = 0;
}
f(1,n,1,n);
}
cout << dp[1][0] << "\n";
for (int i = 1 , go = 1; i <= k ; i++) {
if (from[go][lst] == 1)
from[go][lst] = 2;
cout << from[go][lst] - 1 << " ";
go = from[go][lst--];
}
}
