#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005,MAXK=205;
long long dp[2][MAXN],pref[MAXN]; //max cost dari 1...i dibagi j bagian
int opt[MAXK][MAXN],n;
long long cost(int x,int y){
return (pref[x-1])*(pref[y]-pref[x-1]);
}
void dnc(int L,int R,int optL,int optR,int j){
if(L>R)return;
int mid=(L+R)/2,idx=0;
long long res=-1e18;
for(int i=optL;i<=min(optR,mid-1);i++){
if(dp[(j-1)&1][i]+cost(i+1,mid)>res){
res=dp[(j-1)&1][i]+cost(i+1,mid);
idx=i;
}
}
dp[j&1][mid]=res;
opt[j][mid]=idx;
dnc(L,mid-1,optL,opt[j][mid],j);
dnc(mid+1,R,opt[j][mid],optR,j);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int k,a;
cin >> n >> k;
k++;
for(int i=1;i<=n;i++){
cin >> a;
pref[i]=pref[i-1]+a;
}
for(int i=2;i<=k;i++)dnc(i,n,i-1,n-1,i);
cout << dp[k&1][n] << '\n';
vector<int> id;
int j=n;
for(int i=k;i>=2;i--){
j=opt[i][j];
id.push_back(j);
}
reverse(id.begin(),id.end());
for(int i=0;i<id.size();i++){
if(i<id.size()-1)cout << id[i] << " ";
else cout << id[i] << '\n';
}
return 0;
}
