#include <bits/stdc++.h>
using namespace std;
using i64 = long long; // 64-bit only when it matters
using pii = pair<i64,i64>; // slopes / intercepts still 64-bit
using Line = pair<pii,int>; // (m,c) , id – id fits in 32 bits
deque<Line> hull;
i64 eval(const pii &ln, i64 x) { return ln.first * x + ln.second; }
pair<i64,int> query(i64 x) {
while (hull.size() > 1 &&
eval(hull[0].first, x) < eval(hull[1].first, x))
hull.pop_front();
return { eval(hull[0].first, x) , hull[0].second };
}
long double inter(const pii &a, const pii &b) {
return static_cast<long double>(b.second - a.second) /
static_cast<long double>(a.first - b.first);
}
void insert(i64 m, i64 c, int id) {
pii ln{m,c};
while (hull.size() > 1) {
int s = (int)hull.size();
if (inter(hull[s-1].first, ln) <= inter(hull[s-2].first, ln))
hull.pop_back();
else break;
}
hull.push_back({ln, id});
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
vector<i64> psum(n+1, 0);
vector<vector<i64>> dp(2, vector<i64>(n+1, 0));
/* parent ⟶ 32-bit is enough: it only stores indices ≤ n */
vector<vector<int>> par(k+1, vector<int>(n+1, 0));
for (int i = 1, a; i <= n; ++i) {
cin >> a;
psum[i] = psum[i-1] + a;
}
for (int i = 1; i <= n; ++i)
dp[1][i] = psum[i] * (psum[n] - psum[i]); // base layer
for (int l = 2; l <= k; ++l) {
int cur = l & 1, prv = cur ^ 1;
hull.clear();
for (int i = l; i <= n - k + l; ++i) {
insert(psum[i-1],
dp[prv][i-1] - psum[n] * psum[i-1],
i-1);
auto [best, id] = query(psum[i]);
dp[cur][i] = best + psum[n] * psum[i] - psum[i] * psum[i];
par[l][i] = id; // parent is only 32-bit
}
}
// find optimum
i64 best = LLONG_MIN; int idx = -1;
for (int i = 1; i <= n; ++i)
if (dp[k & 1][i] > best) { best = dp[k & 1][i]; idx = i; }
cout << best << '\n';
/* traceback – parents are still available */
for (int l = k; l && idx; --l) {
cout << idx << ' ';
idx = par[l][idx];
}
return 0;
}
