#include <bits/stdc++.h>
using namespace std;
#define forinc(a, b, c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a, b, c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a, b) for(auto &a : b)
#define rep(i, n) forinc(i, 1, n)
#define repv(i, n) forinc(i, 0, n - 1)
#define ii pair<int,int>
#define fi first
#define se second
#define all(a) begin(a), end(a)
#define reset(f, x) memset(f, x, sizeof(f))
#define eb emplace_back
#define pb push_back
const int N=1e5+5;
long long n,a[N],k,s[N],x[N];
long long f[2][N];
int32_t best[201][N];
void dnc(int id, int l, int r, int u, int v) {
if(l>r) return;
int _=id&1;
int mid=l+(r-l)/2;
f[_][mid]=-1e15;
forinc(i, u, min(mid - 1, v)) {
if(f[_][mid]<=f[_^1][i]+(s[i]*(s[mid]-s[i]))){
best[id][mid]=i;
f[_][mid]=f[_^1][i]+(s[i]*(s[mid]-s[i]));
}
}
dnc(id, l, mid - 1, u, best[id][mid]);
dnc(id, mid + 1, r, best[id][mid], v);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>k;
forinc(i,1,n) cin>>a[i];
forinc(i,1,n) s[i]=s[i-1]+a[i];
fordec(i,n,1) x[i]=x[i+1]+a[i];
forinc(i,1,k){
dnc(i, 1,n, 1,n);
}
cout<<f[k&1][n]<<'\n';
vector<int> ans;
int now=n;
fordec(i,k,1){
ans.pb(best[i][now]);
now=best[i][now];
}
reverse(all(ans));
forv(v, ans) cout << v << ' ';
}
