#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);
vector<ll>m,b;
vector<int>idx;
int ptr;
int path[N][205];
void print(int st,int k)
{
if(path[st][k]==0)
{
cout<<st<<" ";
return;
}
print(path[st][k],k-1);
cout<<st<<" ";
}
bool bad(int f1,int f2,int f3)
{
return (b[f3]-b[f1])*(m[f1]-m[f2])>=(b[f2]-b[f1])*(m[f1]-m[f3]);
}
void add(ll m_,ll b_,int id)
{
m.push_back(m_);
b.push_back(b_);
idx.push_back(id);
int sz=m.size();
while(sz>=3 && bad(sz-3,sz-2,sz-1))
{
m.erase(m.end()-2);
b.erase(b.end()-2);
idx.erase(idx.end()-2);
sz--;
}
}
ll func(int p,ll x)
{
return m[p]*x+b[p];
}
pair<ll,int> get(ll x)
{
if(ptr>=m.size())ptr=m.size()-1;
while(ptr+1<m.size() && func(ptr,x)<=func(ptr+1,x))ptr++;
return {func(ptr,x),idx[ptr]};
}
ll dp[2][N];
ll a[N],pref[N];
int main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
int n,k;
//scanf("%d%d",&n,&k);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
//scanf("%lld",a+i);
pref[i]=pref[i-1]+a[i];
}
for(int i=1;i<=n;i++){
dp[1][i]=pref[i]*(pref[n]-pref[i]);
path[i][1]=0;
}
for(int i=2;i<=k;i++){
int v=(i-1)%2;
m.clear();
b.clear();
idx.clear();
ptr=0;
add(0,0,0);
for(int j=i-1;j<n;j++){
if(j==i-1){
add(-pref[j],dp[v][j],j);
continue;
}
pair<ll,int>tmp=get(pref[n]-pref[j]);
dp[v^1][j]=tmp.first+pref[n]*pref[j]-pref[j]*pref[j];
path[j][i]=tmp.second;
add(-pref[j],dp[v][j],j);
}
//cerr<<m.size()<<' '<<b.size()<<' '<<idx.size()<<'\n';
}
ll mx=0,st=1;
for(int i=1;i<n;i++){
if(dp[k%2][i]>=mx){
mx=dp[k%2][i];
st=i;
}
}
cout<<mx<<endl;
//printf("%lld\n",mx);
print(st,k);
}
