#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "bits/tools.h"
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define debug(x...)
#endif
#define ll long long
#define endl '\n'
const int N = 1e5 + 3,LOG = 27,MOD = 1e9 + 7;
const ll INF = 1e18;
int n,k;
ll a[N],pf[N],dp[2][N];
ll cost(int l,int r){
if(l > r) swap(l,r);
return (pf[r] - pf[l - 1])*pf[l - 1];
// return (pf[r] - pf[l - 1])*(pf[n] - pf[r]);
}
/*
dp[i][j] is the maximum at position j and already had j paritions
dp[i][j] = max(dp[k][j - 1] + cost(k,i))
cost(l,r) = sum(l,r)*sum(r+1,n)
= (pf[r] - pf[l - 1])*(pf[n] - pf[r])
*/
int trace[N][210];
void calc(int l,int r,int ql,int qr,int j){
if(l > r) return;
int mid = (r+l) >> 1;
pair<ll,int> res = {-INF,-1};
for(int i = ql;i <= min(mid,qr);++i)
res = max(res,{dp[(j&1)^1][i - 1] + cost(i,mid),i});
dp[j&1][mid] = res.first;
trace[mid][j] = res.second - 1;
calc(l,mid-1,ql,res.second,j);
calc(mid+1,r,res.second,qr,j);
}
void solver(){
cin>>n>>k;
for(int i = 1;i <= n;++i){
cin>>a[i];
pf[i] = pf[i - 1] + a[i];
}
for(int i = 1;i <= k;++i) calc(1,n,1,n,i);
cout<<dp[k&1][n]<<endl;
int ptr = n; vector<int>path;
for(int i = k;i >= 1;--i){
ptr = trace[ptr][i];
path.push_back(ptr);
}
reverse(path.begin(),path.end());
for(auto i : path) cout<<i<<" ";
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int t = 1; //cin>>t;
while(t--) solver();
}
