#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5;
int n, k;
ll a[MAXN + 1], pre[MAXN + 1];
int trace[MAXN + 1][201];
ll dp[MAXN + 1][201];
int bestPos = 0;
struct Line {
ll a, b;
mutable long double p;
int id;
bool operator<(const Line& other) const { return a < other.a || (a == other.a && b < other.b); }
bool operator<(long double x) const { return p < x; } // heterogeneous lookup
};
struct LINE_CONTAINER {
multiset<Line, less<>> ms;
static constexpr long double INF = 1e30L;
bool isect(multiset<Line, less<>>::iterator x, multiset<Line, less<>>::iterator y) {
if (y == ms.end()) {
x->p = INF;
return false;
}
if (x->a == y->a) {
x->p = (x->b >= y->b ? INF : -INF);
} else {
x->p = (long double)(y->b - x->b) / (long double)(x->a - y->a);
}
return x->p >= y->p;
}
void add(ll slope, ll intercept, int id) {
auto it = ms.insert({slope, intercept, 0.0L, id});
auto z = next(it);
while (isect(it, z)) z = ms.erase(z);
if (it != ms.begin()) {
auto y = prev(it);
if (isect(y, it)) { ms.erase(it); return; }
}
auto y = it;
while (y != ms.begin()) {
auto x = prev(y);
if (isect(x, y)) {
isect(x, ms.erase(y));
y = x;
} else break;
}
}
// trả về {value, id} hoặc {NEG,0} nếu rỗng
pair<ll,int> query(ll X) {
if (ms.empty()) return {LLONG_MIN/4, 0};
auto it = ms.lower_bound((long double)X); // dùng operator<(long double)
if (it == ms.end()) --it;
// tính bằng __int128 để tránh overflow
__int128 val = (__int128)it->a * (__int128)X + (__int128)it->b;
ll out;
if (val > ( (__int128)LLONG_MAX )) out = LLONG_MAX;
else if (val < ( (__int128)LLONG_MIN )) out = LLONG_MIN;
else out = (ll)val;
return {out, it->id};
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> k)) return 0;
for (int i = 1; i <= n; ++i) { cin >> a[i]; pre[i] = pre[i-1] + a[i]; }
const ll NEG = LLONG_MIN / 4;
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= k; ++j) {
dp[i][j] = NEG;
trace[i][j] = 0;
}
dp[0][0] = 0;
vector<LINE_CONTAINER> lc(max(1, k)); // containers for j = 0..k-1
lc[0].add(0LL, 0LL, 0);
for (int i = 1; i <= n; ++i) {
// duyệt j giảm để tránh dùng chính dòng vừa thêm trong cùng i
for (int j = min(i, k); j >= 1; --j) {
auto g = lc[j-1].query(pre[n] - pre[i]);
if (g.first > NEG/2) {
// tính an toàn với __int128
__int128 tmp = (__int128)g.first + (__int128)pre[i] * (__int128)(pre[n] - pre[i]);
ll val;
if (tmp > (__int128)LLONG_MAX) val = LLONG_MAX;
else if (tmp < (__int128)LLONG_MIN) val = LLONG_MIN;
else val = (ll)tmp;
dp[i][j] = val;
trace[i][j] = g.second; // lưu id chỉ khi dp hợp lệ
if (j < k && dp[i][j] > NEG/2) lc[j].add(-pre[i], dp[i][j], i);
if (j == k && i < n && dp[i][k] > dp[bestPos][k]) bestPos = i;
} }
}
cout << dp[bestPos][k] << '\n';
int curPos = bestPos, curK = k;
vector<int> cuts;
while (curPos != 0 && curK > 0) {
cuts.push_back(curPos);
int prev = trace[curPos][curK];
curPos = prev;
--curK;
}
reverse(cuts.begin(), cuts.end());
for (int x : cuts) cout << x << ' ';
cout << '\n';
return 0;
}
