#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<ll, ll>
#define p3i pair<pii, ll>
#define pll pair<ll, int>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define p_q priority_queue
#define MN 1000000009
int pre[100005][205], l2, n, k, a, p[205], lst;
ll ans=-1, t, psa[100005];
deque<pair<ll, int> > mon[205];
void out(int P, int K){
if (K!=0) out(pre[P][K], K-1);
printf("%i ", P);
}
ll cross(pll A, pll O, pll B){
return (A.x-O.x)*(-psa[B.y]+psa[O.y])-(B.x-O.x)*(-psa[A.y]+psa[O.y]);
}
void add(ll K, pair<ll, int> P){
while(mon[K].size()>p[K]+1 && cross(mon[K][mon[K].size()-2], mon[K].back(), P)<=0){
mon[K].pop_back();
}
mon[K].pb(P);
}
int main(){
mon[0].pb(mp(0, 0));
cin >> n >> k;
for (int l=1; l<=n; ++l){
cin >> a; psa[l]=a+psa[l-1];
}
for (int l=1; l<=n; ++l){
for (l2=k-1; l2>=0; --l2){
if (mon[l2].empty()) continue;
while(p[l2]+1<mon[l2].size() &&
(psa[n]-psa[l])*(psa[l]-psa[mon[l2][p[l2]].y])+mon[l2][p[l2]].x<=
(psa[n]-psa[l])*(psa[l]-psa[mon[l2][p[l2]+1].y])+mon[l2][p[l2]+1].x)
mon[l2].pop_front();//, cout << "*";
pre[l][l2]=mon[l2][p[l2]].y;
t=(psa[n]-psa[l])*(psa[l]-psa[mon[l2][p[l2]].y])+mon[l2][p[l2]].x;
//cout << t << ' ' ;
if (l2==k-1 && t>ans){
ans=t; lst=l;
}
add(l2+1, mp(t, l));
}
//cout << endl;
}
cout << ans << endl;
if (lst!=-1) out(lst, k-1);
return 0;
}
