#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 2e18;
ll pre[100'010][210];
struct LiChao_max {
struct line {
ll a, b;
ll in;
line(){a=0,b=0;}
line(ll _a, ll _b, ll _in){a=_a,b=_b,in=_in;}
ll val(ll x){return a*x+b;}
};
struct node {
line f;
node* l, *r;
node(){f=line(),l=nullptr,r=nullptr;}
node(line v){f=v,l=nullptr,r=nullptr;}
node(ll a, ll b, ll in){f=line(a, b, in),l=nullptr,r=nullptr;}
};
ll sz;
node* root;
void init(ll _sz){sz=_sz+1,root=nullptr;}
void add_line(ll a, ll b, ll in){line v = line(a, b, in);insert(v, -sz, sz, root);}
line query(ll x){return query(x, -sz, sz, root);}
void insert(line v, ll l, ll r, node*& nd) {
if(nd == nullptr){nd=new node(v);return;}
ll tl = nd->f.val(l), tr = nd->f.val(r);
ll vl = v.val(l), vr = v.val(r);
if(tl >= vl and tr >= vr)return;
if(tl < vl and tr < vr){std::swap(nd->f, v);return;}
if(tl < vl)std::swap(nd->f, v);
ll mid = (l+r)/2;
if(nd->f.val(mid) < v.val(mid)) {
std::swap(nd->f, v);
insert(v, l, mid, nd->l);
}
else {
insert(v, mid+1, r, nd->r);
}
}
line query(ll x, ll l, ll r, node*& nd) {
if(nd == nullptr)return line(0, 0, -1);
if(l == r)return nd->f;
ll mid = (l+r)/2;
if(x <= mid) {
line v = query(x, l, mid, nd->l);
if(v.val(x) > nd->f.val(x))return v;
return nd->f;
}
else {
line v = query(x, mid+1, r, nd->r);
if(v.val(x) > nd->f.val(x))return v;
return nd->f;
}
}
};
int main () {
LiChao_max l;
int n, k;
cin >> n >> k;
long long arr[n];
for(int i = 0;i<n;i++) {
cin >> arr[i];
}
long long pref[n+1];
pref[0] = 0;
for(int i = 1;i<=n;i++)pref[i] = pref[i-1] + arr[i-1];
vector<long long> dp[2];
for(int i = 0;i<2;i++)dp[i].resize(n+1);
for(int j = 0;j<k;j++) {
l.init(1e9 + 10);
l.add_line(0,0, -1);
for(int i = 1;i<=n;i++) {
pre[i-1][j] = -1;
LiChao_max::line v = l.query(pref[n]-pref[i]);
dp[1][i] = v.val(pref[n]-pref[i]) + pref[i]*(pref[n]-pref[i]);
l.add_line(-pref[i], dp[0][i], i-1);
pre[i-1][j]=v.in;
if(j == 0)pre[i-1][j] = -1;
// cout << dp[1][i] << " ";
}
dp[0].swap(dp[1]);
}
ll mx = -1, idx = -1;
for(int i = 0;i<n;i++) {
if(dp[0][i+1] >= mx) {
mx = dp[0][i+1];
idx = i;
}
}
cout << mx << "\n";
k--;
while(idx!=-1 and k >= 0) {
cout << idx+1 << " ";
idx = pre[idx][k];
k--;
}
cout << "\n";
}
