#include <bits/stdc++.h>
#define DIM 100010
#define DIMK 210
#define ll long long
using namespace std;
int v[DIM],d[DIM];
ll dp[DIM][2],sp[DIM];
vector <int> sol;
map <pair<int,int>,int> fth;
int n,k,i,j,p,u;
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 main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>k;
for (i=1;i<=n;i++){
cin>>v[i];
sp[i] = sp[i-1] + v[i];
}
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 * (-1);
//fth[i][j] = sol.second;
fth[make_pair(i,j)] = sol.second;
}
t = 1-t;
}
int x, y = k;
ll maxi = -1;
for (i=1;i<n;i++)
if (dp[i][1-t] > maxi)
maxi = dp[i][1-t], x = i;
cout<<maxi<<"\n";
sol.push_back(x);
while (x){
sol.push_back(fth[make_pair(x,y)]);
x = fth[make_pair(x,y)];
y--;
}
for (i=sol.size()-2;i>=0;i--)
cout<<sol[i]<<" ";
return 0;
}
