#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, a[200010], dp[2][100010];
int32_t tv[203][100010];
int c(int l, int r)
{
return (a[r] - a[l-1]) * (a[n] - a[r]);
}
void calculate(int p, int l, int r, int tl, int tr)
{
if(l > r) return;
int bestval = -1, bestplace = 0, mid = (l+r)/2;
for(int i = tl; i <= tr; i++) if(i <= mid && i >= p){
int curval = dp[(p&1)^1][i-1] + c(i, mid);
if(bestval < curval){
bestval = curval;
bestplace = i;
}
}
dp[p&1][mid] = bestval; tv[p][mid] = bestplace;
calculate(p, l, mid-1, tl, bestplace);
calculate(p, mid+1, r, bestplace, tr);
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int k;
cin>>n>>k;
k++;
for(int i = 1; i <= n; i++) cin>>a[i];
for(int i = 1; i <= n; i++) a[i] += a[i-1];
for(int i = 1; i <= k; i++) calculate(i, i, n, 1, n);
/*for(int i = 1; i <= k; i++){
for(int j = 1; j <= n; j++) cout<<dp[i][j]<<" ";
cout<<endl;
}*/
cout<<dp[k&1][n]<<'\n';
vector<int> ans; int place = n;
for(int i = k; i > 1; i--){
place = tv[i][place]-1;
ans.push_back(place);
}
reverse(ans.begin(), ans.end());
for(int i : ans) cout<<i<<" ";
}
