#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define FOR for(int i=1;i<=n;i++)
const int lim=100002;
typedef long long lo;
int n,k;
int dizi[lim];
lo pre[lim];
lo dp[lim][2];
int yol[lim][202];
int q[lim];
inline bool cont(int x,int y,int cur){
if(dp[y][0]-pre[y]*(pre[n]-pre[cur])>=dp[x][0]-pre[x]*(pre[n]-pre[cur]))return 1;
return 0;
}
inline bool cont2(int x,int y,int cur){
if((dp[y][0]-dp[x][0])*(pre[cur]-pre[y])<=(dp[cur][0]-dp[y][0])*(pre[y]-pre[x]))return 1;
return 0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n>>k;
FOR{
cin>>dizi[i];
pre[i]=pre[i-1]+dizi[i];
}
int l,r;
for(int i=1;i<=k;i++){
l=1,r=1;
q[l]=0;
for(int j=1;j<=n;j++){
while(r-l>0 && cont(q[l],q[l+1],j))l++;
dp[j][1]=dp[q[l]][0]+(pre[j]-pre[q[l]])*(pre[n]-pre[j]);
yol[j][i]=q[l];
while(r-l>0 && cont2(q[r-1],q[r],j))r--;
q[++r]=j;
}
for(int j=1;j<=n;j++){
dp[j][0]=dp[j][1];
}
}
lo cev=-5;
int bas=0;
for(int i=n-1;i>=1;i--){
if(cev<dp[i][0]){
cev=dp[i][0];
bas=i;
}
}
cout<<cev<<'\n';
for(int i=k;i>=1;i--){
cout<<bas<<" ";
bas=yol[bas][i];
}
cout<<'\n';
}
