#include <bits/stdc++.h>
#define int long long
const int maxn = 1e5 + 5;
const long long INF = 1e18;
int n, k;
int trace[maxn + 5][205];
int a[maxn + 5], pref[maxn + 5];
long long f_prev[maxn + 5], f[maxn + 5];
long long divi(long long x, long long y) {
if (!x || !y) return 0ll;
return x / y - ((x ^ y) < 0 && x % y);
}
struct line {
int pos;
long long a, b;
line(long long _a, long long _b, int _pos) : a(_a), b(_b), pos(_pos) {}
long long operator () (long long x) { return a * x + b; }
long long intersect(const line &other) {
return divi(other.b - b, a - other.a);
}
};
bool check(line l1, line l2, line l3) {
int b23 = l3.b - l2.b;
int a23 = l2.a - l3.a;
int b12 = l2.b - l1.b;
int a12 = l1.a - l2.a;
if (a23 < 0) {
b23 *= -1;
a23 *= -1;
}
if (a12 < 0) {
b12 *= -1;
a12 *= -1;
}
return b23 * a12 >= b12 * a23;
}
bool check_intersect(line l1, line l2, int x) {
int b12=(l2.b-l1.b);
int a12=(l1.a-l2.a);
if(a12<0){
a12*=-1;
b12*=-1;
}
return b12<x*a12;
}
struct CHT {
std::vector<line> data_line;
void add(line d) {
while ((int)data_line.size() >= 2 &&
check(data_line[(int)data_line.size() - 2], data_line[(int)data_line.size() - 1], d)) {
data_line.pop_back();
}
data_line.push_back(d);
}
int query(long long x) {
int l = 0, r = (int)data_line.size() - 1, pos;
while (l <= r) {
int mid = (l + r) >> 1;
if (!mid) {
pos=mid;
l=mid+1;
continue;
}
if (check_intersect(data_line[mid], data_line[mid - 1], x)) {
r = mid - 1;
} else {
l = mid + 1;
pos = mid;
}
}
line d = data_line[pos];
return d.pos;
}
};
void solve() {
std::cin >> n >> k;
for (int i = 1; i <= n; ++i) std::cin >> a[i];
for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + a[i];
for (int i = 1; i < n; ++i)
f_prev[i] = 1ll * (pref[n] - pref[i]) * pref[i];
int pos_ans;
long long ans = -1;
if (k == 1) {
for (int i = 1; i < n; ++i)
if (ans < f_prev[i]) {
ans = f_prev[i];
pos_ans = i;
}
std::cout << ans << '\n';
std::cout << pos_ans;
return;
}
for (int j = 2; j <= k; ++j) {
CHT lc;
for (int i = j; i < n; ++i) {
// f[i][j] = (pref[i] - pref[l]) * (pref[n] - pref[i]) + f[l][j - 1];
// = (pref[n] - pref[i]) * pref[i] - (pref[n] - pref[i]) * pref[l] + f[l][j - 1];
lc.add(line(1ll * -pref[i - 1], f_prev[i - 1], i - 1));
int pos = lc.query(1ll * pref[n] - pref[i]);
f[i] = 1ll * (pref[n] - pref[i]) * pref[i] + 1ll * -pref[pos] * (pref[n] - pref[i]) + f_prev[pos];
trace[i][j] = pos;
if (j == k) {
if (ans < f[i]) {
ans = f[i];
pos_ans = i;
}
}
}
for (int i = 1; i < n; ++i) f_prev[i] = f[i];
}
std::vector<int> pos_vec;
while (k) {
assert(pos_ans > 0);
pos_vec.push_back(pos_ans);
pos_ans = trace[pos_ans][k];
k--;
}
reverse(pos_vec.begin(), pos_vec.end());
std::cout << ans << '\n';
for (int x : pos_vec) std::cout << x << ' ';
}
signed main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int tc = 1;
// std::cin >> tc;
while (tc--)
solve();
}
