#include<bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int N=1e5+12;
int n,k,T,IT;
int gr[220][N];
ll pr[N],dp[2][N];
void rec(int tl,int tr,int tpl=1,int tpr=n){
if(tl>tr)return;
int tm=(tl+tr)/2,tp=0;
ll curs=-1;
for(int i=max(tpl,IT-1);i<=min(tm-1,tpr);i++){
if(dp[1-T][i]+pr[i]*(pr[tm]-pr[i])>curs)
curs=dp[1-T][i]+pr[i]*(pr[tm]-pr[i]),tp=i;
}
dp[T][tm]=curs,gr[IT][tm]=tp;
rec(tl,tm-1,tpl,tp);
rec(tm+1,tr,tp,tpr);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>pr[i];
pr[i]+=pr[i-1];
}
k+=1;
for(int i=2;i<=k;i++){
T=i&1,IT=i;
rec(1,n);
}
cout << dp[k & 1][n] << "\n";
for(int j = k, pos = n;j > 1;j--){
cout << gr[j][pos] << " ";
pos = gr[j][pos];
}
}
