#include <vector>
#include <iostream>
#include <utility>
#include <deque>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define ld long double
#define dq deque
#define pll pair<ll,ll>
struct line{
ld m=0;
ld c=0;
ll ind=0;
};
ld inter(line a, line b){
return (a.c-b.c)/(b.m-a.m);
}
dq<line> cht;
void add(ld m, ld c, ll ind){
line x;
x.m=m;
x.c=c;
x.ind=ind;
while(cht.size()>1){
line back=cht.back();
cht.pop_back();
ld one=inter(x,back);
ld two=inter(back,cht.back());
if(one>two){
cht.push_back(back);
break;
}
}
cht.push_back(x);
}
line query(ll x){
while(cht.size()>1){
line front=cht.front();
cht.pop_front();
if(front.m*x + front.c > cht.front().m * x + cht.front().c){
cht.push_front(front);
break;
}
}
return cht.front();
}
int main(){
int N,K;
cin>>N>>K;
v<ll> vals(N);
for(int i=0;i<N;i++) cin>>vals[i];
v<ll> prefix;
prefix.push_back(vals[0]);
for(int i=1;i<N;i++) prefix.push_back(prefix.back() + vals[i]);
v<v<int>> from(K+2,v<int>(N+2,-1));
v<v<ll>> dp(K+2,v<ll>(N+2,0));
for(int k=1;k<=K;k++){
cht=dq<line>(0);
for(int i=k-1;i<N-1;i++){
if(i==0){
dp[k][i]=prefix[i] * (prefix[N-1]-prefix[i]);
from[k][i]=0;
continue;
}
//add j=i to cht
if(vals[i-1]!=0) add(prefix[i-1], dp[k-1][i-1]- prefix[N-1] * prefix[i-1], i-1);
//query x=prefix[i], also need to store j values in cht
line q=query(prefix[i]);
dp[k][i] = (prefix[i] * (prefix[N-1]-prefix[i])) + (q.m * prefix[i] + q.c);
from[k][i] = q.ind;
/**
ll val=0;
int ind=0;
for(int j=k-1;j<=i;j++){
ll tmp=prefix[i] * (prefix[N-1]-prefix[i]);
tmp+=prefix[j-1]*prefix[i];
tmp+=dp[k-1][j-1] - prefix[N-1] * prefix[j-1];
val=max(val, tmp);
if(val==tmp) ind=j-1;
}
dp[k][i]=val;
from[k][i]=ind;**/
}
}
ll out=0;
int ind=0;
for(int i=0;i<N-1;i++){
out=max(out, dp[K][i]);
if(out==dp[K][i]) ind=i;
}
cout<<out<<endl;
for(int k=K;k>0;k--){
cout<<ind+1<<" ";
ind=from[k][ind];
}
cout<<endl;
}
