#include <bits/stdc++.h>
#define DIM 100001
#define DIMBUFF 5000000
#define ll long long
using namespace std;
ll dp[DIM][2];
ll sp[DIM];
vector <int> sol;
int fth[DIM][201];
int n,k,i,j,p,u,val,pos;
char buff[DIMBUFF];
struct cmp{
bool operator()(pair<pair<ll,ll>,int> x, pair<pair<ll,ll>,int> y){
if (x.first.first == y.first.first)
return x.first.second < y.first.second;
return x.first.first > y.first.first; /// descrescator dupa panta
}
};
set <pair<pair<ll,ll>,int>,cmp> s;
bool intersectie (pair <ll,ll> c, pair <ll,ll> b, pair <ll,ll> a){
return (a.second-c.second)*(b.first-a.first) < (a.second-b.second)*(c.first-a.first);
}
void add (ll a, ll b, int i){
set <pair<pair<ll,ll>,int> > ::iterator it = s.find(make_pair(make_pair(a,b),i));
if (it != s.end() && it->first.first == a && it->first.second == b)
return;
it = s.lower_bound(make_pair(make_pair(a,b),i));
if (it != s.begin()){
it--;
int ok = 1;
do{
if (it != s.begin()){
set <pair<pair<ll,ll>,int> > :: iterator it2 = it;
it2--;
if (intersectie(make_pair(a,b),make_pair(it->first.first,it->first.second),make_pair(it2->first.first,it2->first.second))){
s.erase(it);
it = it2;
} else ok = 0;
} else ok = 0;
} while (ok);
}
it = s.lower_bound(make_pair(make_pair(a,b),i));
if (it != s.begin() && it != s.end()){
set <pair<pair<ll,ll>,int> > :: iterator it2 = it;
it2--;
if (intersectie (make_pair(it->first.first,it->first.second),make_pair(a,b),make_pair(it2->first.first,it2->first.second)) == 0){
s.insert(make_pair(make_pair(a,b),i));
return;
}}
else s.insert(make_pair(make_pair(a,b),i));
}
pair<ll,int> query (ll x){
/// daca am query uri crescatoare pot sa sterg din fata
set <pair<pair<ll,ll>,int> > :: iterator it = s.begin();
while (it != s.end()){
set <pair<pair<ll,ll>,int> > :: iterator it2 = it;
it2++;
if (it2 == s.end())
break;
if (it->first.first * x + it->first.second > it2->first.first * x + it2->first.second){
/// il sterg pe it
s.erase(it);
it = it2;
} else break;
}
return make_pair(it->first.first * x + it->first.second, it->second);
}
int get_nr(){
while (!(buff[pos] >= '0' && buff[pos] <= '9'))
pos++;
int nr = 0;
while (buff[pos] >= '0' && buff[pos] <= '9'){
nr = nr * 10 + buff[pos] - '0';
pos++;
}
return nr;
}
int main (){
//FILE *fin = fopen ("date.in","r");
//FILE *fout = fopen ("date.out","w");
FILE *fin = stdin;
FILE *fout = stdout;
fread (buff,1,DIMBUFF,fin);
n = get_nr(), k = get_nr();
for (i=1;i<=n;++i){
val = get_nr();
sp[i] = sp[i-1] + val;
}
for (i=1;i<n;++i)
dp[i][1] = sp[i] * (sp[n] - sp[i]);
int t = 0;
for (j=2;j<=k;++j){
s.clear();
for (i=j;i<n;++i){
add (-sp[i-1],-(dp[i-1][1-t] - sp[i-1] * sp[n]),i-1);
pair <ll, int> sol = query (sp[i]);
dp[i][t] = sp[i] * sp[n] - sp[i] * sp[i] - sol.first;
//fth[i][j] = sol.second;
fth[i][j] = sol.second;
}
t = 1-t;
}
int x, y = k;
ll maxi = -1;
for (i=k;i<n;++i)
if (dp[i][1-t] > maxi)
maxi = dp[i][1-t], x = i;
//cout<<maxi<<"\n";
fprintf(fout,"%lld\n",maxi);
sol.push_back(x);
while (x){
sol.push_back(fth[x][y]);
x = fth[x][y];
y--;
}
for (i=sol.size()-2;i>=0;--i)
fprintf(fout,"%d ",sol[i]);
//cout<<sol[i]<<" ";
return 0;
}
