#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e9;
ll orientation(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c){
return (c.first-b.first)*(b.second-a.second)-(b.first-a.first)*(c.second-b.second);
}
void solve(){
int n, K;
cin>>n>>K;
vector<ll> a(n+1), p(n+1);
for(ll i=1;i<=n;i++){
cin>>a[i];
p[i]=p[i-1]+a[i];
}
vector<vector<ll>> dp(n+1, vector<ll>(K+1, -inf));
for(ll i=1;i<=n;i++){
dp[i][0]=0;
}
for(ll k=1;k<=K;k++){
deque<pair<ll, ll>> ch;
ch.push_back({ -1e9, -1e9 });
for(ll i=1;i<=n;i++){
//get max at p[i] in hull
ll x=p[i];
while(ch.size()>1ll&&ch[1].first*x+ch[1].second>=ch[0].first*x+ch[0].second){
ch.pop_front();
}
dp[i][k]=max(dp[i][k], ch[0].first*x+ch[0].second);
ll c=dp[i][k-1]-p[i]*p[i];
ll m=p[i];
while(ch.size()>1&&orientation(ch[ch.size()-2], ch[ch.size()-1], { m, c })<=0ll){
ch.pop_back();
}
ch.push_back({ m, c });
}
}
vector<ll> seq;
for(ll k=K, i=n, j=n-1;k>=1;){
if(dp[j][k-1]+(p[i]-p[j])*p[j]==dp[i][k]){
seq.push_back(j);
i=j;
k--;
}
else j--;
}
reverse(seq.begin(), seq.end());
cout<<dp[n][K]<<endl;
for(auto& i:seq)cout<<i<<" ";
cout<<endl;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t=1;
// cin>>t;
while(t--){
solve();
}
}
