#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
using ll = long long;
struct Line {
ll m = 0, c = 0, id = 0;
Line(ll _m, ll _c, ll _id) : m(_m), c(_c), id(_id) { }
ll get(ll x) { return m * x + c; }
double intersection(Line o) { return (double) (o.c - c) / (double) (m - o.m); }
bool good(Line l2, Line l3) { return __int128(l2.c - c) * (l2.m - l3.m) < __int128(l3.c - l2.c) * (m - l2.m); }
};
struct CHT {
deque<Line> hull;
void insert(Line l) {
while (hull.size() > 1) {
auto last = hull.end()[-1];
auto p_last = hull.end()[-2];
if (p_last.good(last, l)) break;
hull.pop_back();
}
hull.push_back(l);
}
pair<ll, ll> query(ll x) {
while (hull.size() > 1 && hull[0].get(x) < hull[1].get(x)) {
hull.pop_front();
}
return {hull[0].get(x), hull[0].id};
}
};
int par[100002][202];
void testCase() {
int n, K;
cin >> n >> K;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] += a[i - 1];
}
vector<ll> dp(n + 1);
for (int k = 1; k <= K + 1; k++) {
vector<ll> new_dp(n + 1);
CHT cht;
cht.insert(Line(a[k - 1], dp[k - 1] - a[k - 1] * a[n], k - 1));
for (int i = k; i <= n; i++) {
auto [x, id] = cht.query(a[i]);
par[i][k] = id;
x += a[n] * a[i] - a[i] * a[i];
new_dp[i] = x;
cht.insert(Line(a[i], dp[i] - a[n] * a[i], i));
}
// debug(new_dp);
if (k == K + 1) {
cout << new_dp[n] << "\n";
}
dp = new_dp;
}
vector<int> ans;
{
int cur = n;
int k = K + 1;
while (cur) {
ans.push_back(cur);
cur = par[cur][k];
k--;
}
}
reverse(ans.begin(), ans.end());
ans.pop_back();
for (int i : ans) cout << i << " ";
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
testCase();
return 0;
}
