#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <limits.h>
using namespace std;
inline namespace _LineContainer {
bool _Line_Comp_State;
struct Line {
mutable long long k, m, p;
int id;
bool operator<(const Line& o) const {
return _Line_Comp_State ? make_pair(p, id) < make_pair(o.p, o.id) : make_pair(k, id) < make_pair(o.k, o.id);
}
};
struct LineContainer : multiset<Line> {
long long div(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) {
x->p = LLONG_MAX;
return false;
}
if (x->k == y->k)
x->p = x->m > y->m ? LLONG_MAX : -LLONG_MAX;
else
x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(long long k, long long m, int id) {
auto z = insert({k, m, 0, id}), y = z++, x = y;
while (isect(y, z))
z = erase(z);
if (x != begin() && isect(--x, y))
isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
pair<long long, long long> query(long long x) {
assert(!empty());
_Line_Comp_State = 1;
auto l = *lower_bound({0,0,x, -1});
_Line_Comp_State = 0;
return {l.k * x + l.m, l.id};
}
};
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
int64_t arr[n]; int64_t pref[n + 1]; pref[0] = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
pref[i + 1] = pref[i] + arr[i];
}
int64_t dp[n - 1][k + 1];
int64_t prev[n - 1][k + 1];
for (int i = 0; i < n - 1; i++) {
dp[i][1] = (pref[i + 1]) * (pref[n] - pref[i + 1]);
prev[i][1] = -1;
}
for (int j = 2; j <= k; j++) {
LineContainer cht;
dp[0][j] = 0;
for (int i = 1; i < n - 1; i++) {
cht.add(pref[i], dp[i - 1][j - 1], i);
auto p = cht.query(pref[i + 1] - pref[n]);
dp[i][j] = max(p.first, 0ll) + pref[i + 1] * pref[n] - pref[i + 1] * pref[i + 1];
prev[i][j] = p.second - 1;
}
}
int64_t myMax = 0;
for (int i = 0; i < n - 1; i++) {
myMax = max(myMax, dp[i][k]);
}
cout << myMax << '\n';
for (int i = 0; i < n - 1; i++) {
if (myMax == dp[i][k]) {
int mid = i;
int cntr = 0;
while (cntr != k) {
cout << mid + 1 << ' ';
mid = prev[mid][k - cntr];
cntr++;
}
return 0;
}
}
}
