// #include <bits/stdc++.h>
// using namespace std;
// #define int long long
// template<typename T>
// string tostr(const T& value) {
// ostringstream oss;
// oss << value;
// return oss.str();
// }
// template<typename... Args>
// string fstr(const string& format, Args... args) {
// string result = format;
// size_t pos = 0;
// size_t argIndex = 0;
// auto replaceArg = [&](const auto& arg) {
// pos = result.find("{}", pos);
// if (pos != string::npos) {
// result.replace(pos, 2, tostr(arg));
// ++argIndex;
// }
// };
// (replaceArg(args), ...);
// return result;
// }
// const int maxn = 100000;
// const int maxk = 200;
// const int INF = 2000000000000000;
// int n, k;
// int v[maxn+1];
// int dp[maxn+1][2];
// int p[maxn+1][maxk+1];
// struct F {
// int a, b;
// bool operator<(F o) const { return a*o.b<b*o.a; }
// };
// struct L {
// int m, b, i;
// int f(int x) { return m*x+b; }
// F operator^(L o) { return F{b-o.b,o.m-m}; }
// };
// struct CHT {
// deque<L> d;
// void add(L l) {
// while (d.size() >= 2 && (d.end()[-2]^l) < (d.end()[-2]^d.back())) d.pop_back();
// d.push_back(l);
// }
// L qry(int x) {
// while (d.size() >= 2 && d[1].f(x) > d[0].f(x)) d.pop_front();
// // for (auto i : d) cout << fstr("({}, {}, {}) ", i.m, i.b, i.i);
// // cout << endl;
// return d[0];
// }
// };
// signed main() {
// cin.tie(nullptr) -> ios::sync_with_stdio(false);
// // freopen("main.in", "r", stdin);
// cin >> n >> k;
// for (int i = 1; i <= n; i++) { cin >> v[i]; v[i] += v[i-1]; }
// fill(dp[0], dp[0] + 2*(maxn+1), -INF);
// dp[0][0 & 1] = 0;
// for (int i = 1; i <= k; i++) {
// CHT h;
// for (int j = 1; j <= n; j++) {
// h.add(L{v[j-1], dp[j-1][(i-1)&1] - v[j-1] * v[j-1], j-1});
// L l = h.qry(v[j]);
// dp[j][i&1] = max(l.f(v[j]), -INF);
// p[j][i] = l.i;
// // cout << fstr("{} {} {} {} {}", i, j, i&1, j&1, (i-1)&1) << endl;
// // cout << fstr("(i {}) (j {}) (dp[j-1][(i-1)&1] {}) (dp[j][i&1] {})", i, j, dp[j-1][(i-1)&1], dp[j][i&1]) << endl;
// }
// // cout << endl;
// }
// int ans = -INF;
// for (int i = 0; i <= n; i++)
// ans = max(ans, (v[n] - v[i]) * v[i] + dp[i][k & 1]);
// cout << ans << endl;
// for (int i = 0; i <= n; i++)
// if ((v[n] - v[i]) * v[i] + dp[i][k&1] == ans) {
// while (k) {
// cout << i << ' ';
// i = p[i][k--];
// }
// }
// return 0;
// }
#include <bits/stdc++.h>
using namespace std;
template<typename T>
string tostr(const T& value) {
ostringstream oss;
oss << value;
return oss.str();
}
template<typename... Args>
string fstr(const string& format, Args... args) {
string result = format;
size_t pos = 0;
size_t argIndex = 0;
auto replaceArg = [&](const auto& arg) {
pos = result.find("{}", pos);
if (pos != string::npos) {
result.replace(pos, 2, tostr(arg));
++argIndex;
}
};
(replaceArg(args), ...);
return result;
}
#define int long long
const int maxn = 100000;
const int maxk = 200 + 1;
const int INF = 2000000000'000000;
int n, k;
int v[maxn+1];
int dp[maxn+1][2];
int p[maxn+1][maxk+1];
struct F { int a, b; bool operator<(F o) const { return a*o.b<b*o.a; } };
struct L {
int m, b, i;
int f(int x) { return m*x+b; }
F operator*(L o) { return F{b-o.b,o.m-m}; }
};
struct CHT {
deque<L> d;
inline void clear() { d.clear(); }
void add(L l) {
while (d.size() >= 2 && (d.end()[-2]*l) < (d.end()[-2]*d.back())) d.pop_back();
d.push_back(l);
}
L qry(int x) {
while (d.size() >= 2 && d[1].f(x) > d[0].f(x)) d.pop_front();
return d[0];
}
};
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++) { cin >> v[i]; v[i] += v[i-1]; }
fill(dp[0], dp[0] + (maxn+1), 0);
fill(dp[0] + (maxn+1), dp[0] + (maxn+1)*2, -INF);
dp[0][0] = -INF;
for (int i = 1; i <= k; i++) {
CHT h;
dp[0][i&1] = -INF;
for (int j = 1; j <= n; j++) {
h.add(L{v[j-1], dp[j-1][(i-1)&1] - v[j-1]*v[j-1], j-1});
L q = h.qry(v[j]);
dp[j][i&1] = max(q.f(v[j]), -INF);
p[j][i] = q.i;
}
}
cout << dp[n][k & 1] << endl;
int x = p[n][k--];
while (k + 1) {
cout << x << ' ';
x = p[x][k--];
}
}
signed main() {
// freopen("main.in", "r", stdin);
int t;
// cin >> t;
t=1;
while(t--) solve();
return 0;
}
