#include <bits/stdc++.h>
using namespace std;
#define N 100011
#define K 202
#define INF (long long)(1e18 + 36)
int n, k, trace[K][N];
long long a[N], dp[2][N];
void calc(int t,int l,int r,int opl,int opr){
if(l > r)return;
int mid = (l + r) >> 1;
pair<long long, int> best = {-INF * 3, -1};
for(int p = opl; p <= min(mid, opr); p++){
long long C = dp[0][p - 1] + (a[mid] - a[p - 1]) * (a[n] - a[mid]);
if(C > best.first){
best = {C, p};
}
}
dp[1][mid] = best.first;
trace[t][mid] = best.second - 1;
calc(t, l, mid - 1, opl, best.second);
calc(t, mid + 1, r, best.second, opr);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>k;
k++;
for(int i = 1; i <= n; i++)cin>>a[i], a[i] += a[i - 1];
for(int j = 0; j <= n; j++)
dp[0][j] = dp[1][j] = -INF;
dp[0][0] = 0;
for(int t = 1; t <= k; t++){
calc(t, 1, n, 1, n);
swap(dp[0], dp[1]);
dp[1][0] = -INF;
}
cout<<dp[0][n]<<'\n';
int u = trace[k][n];
k--;
vector<int> ans;
while(u){
ans.push_back(u);
u = trace[k][u];
k--;
}
reverse(ans.begin(), ans.end());
for(int x : ans)cout<<x<<' ';
}
