#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const ll linf = 1e18 + 1;
struct ftype{
ll k, b, ind;
ftype(ll k, ll b, ll ind) : k(k), b(b), ind(ind){
}
ftype(){
k = b = ind = 0;
}
ll get(ll x){
return k * x + b;
}
};
vector <ftype> t;
vector <int> le, ri;
ll L = 0, R ;
vector <ll> suf;
map<int, int> mp;
bool comp(ftype a, ftype b, ll x){
return a.get(suf[x - 1]) > b.get(suf[x - 1]);
}
void addline(int v, ll l, ll r, ftype nw){
ll m = (l + r) / 2;
bool f1 = comp(nw, t[v], l);
bool f2 = comp(nw, t[v], m);
if(f2) swap(t[v], nw);
if(l == r) return;
if(f1 != f2){
int x = le[v];
if(x == 0){
le[v] = t.size();
t.pb(nw);
le.pb(0);
ri.pb(0);
}
addline(le[v], l, m, nw);
}
else{
int x = ri[v];
if(x == 0){
ri[v] = t.size();
t.pb(nw);
le.pb(0);
ri.pb(0);
}
addline(ri[v], m + 1, r, nw);
}
}
ftype query(int v, ll l, ll r, ll x){
if(l == r) return t[v];
ll m= (l + r) / 2;
if(x <= m){
if(le[v] == 0) {
return t[v];
}
ftype nw = query(le[v], l, m, x);
if(nw.get(suf[x - 1]) > t[v].get(suf[x - 1])) return nw;
return t[v];
}
if(ri[v] == 0) {
return t[v];
}
ftype nw = query(ri[v], m + 1, r, x);
if(nw.get(suf[x - 1]) > t[v].get(suf[x - 1])) return nw;
return t[v];
}
ll dp[100001][201];
ll p[100001][201];
int main(){
int n, k; cin >> n >> k;
ll a[n + 1];
ll pref[n + 1];
pref[0] = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
for(int i = 0; i <= n; i++){
suf.pb(pref[n] - pref[i]);
}
L = 1, R = n + 1;
sort(suf.begin(), suf.end());
for(int i = 0; i < suf.size(); i++){
mp[suf[i]] = i + 1;
}
for(int i = 0; i <= n; i++){
for(int j = 0; j <= k; j++) dp[i][j] = -linf;
}
dp[0][0] = 0;
for(int i = 1; i <= k; i++){
t.clear();
le.clear();
ri.clear();
t.pb({-10, -linf, -1});
t.pb({-10, -linf, -1});
le.pb(0);
le.pb(0);
ri.pb(0);
ri.pb(0);
addline(1, L, R, {0, dp[0][i - 1], 0});
for(int j = 1; j <= n; j++){
ll x = pref[n] - pref[j];
x = mp[x];
ftype res = query(1, L, R, x);
dp[j][i] = max(pref[j] * (pref[n] - pref[j]) + res.get(suf[x - 1]), dp[j][i]);
p[j][i] = res.ind;
addline(1, L, R, {-pref[j], dp[j][i - 1], j});
}
}
ll ans = -1;
int ansi;
for(int i = 1; i <= n; i++){
if(dp[i][k] > ans) ans = dp[i][k], ansi = i;
}
cout << ans << "\n";
int cnt = k;
vector <int> vec;
while(cnt){
vec.pb(ansi);
ansi = p[ansi][cnt--];
}
reverse(vec.begin(), vec.end());
for(int to : vec) cout << to << ' ';
return 0;
}
