#include <bits/stdc++.h>
using namespace std;
#pragma region debug
#ifndef NDEBUG
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
return os << '(' << p.first << ", " << p.second << ')';
}
template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}
template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << '[';
if (v.size()) {
os << *v.begin();
for (auto i = ++v.begin(); i != v.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &v) {
os << '[';
if (N) {
os << *v.begin();
for (auto i = ++v.begin(); i != v.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &s) {
os << '[';
if (s.size()) {
os << '(' << s.begin()->FF << " : " << s.begin()->SS << ')';
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << '(' << i->FF << " : " << i->SS << ')';
}
return os << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const unordered_map<T1, T2>& s) {
os << '[';
if (s.size()) {
os << '(' << s.begin()->FF << " : " << s.begin()->SS << ')';
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << '(' << i->FF << " : " << i->SS << ')';
}
return os << ']';
}
#define dbg1(a) cerr << #a << " = " << a << '\n';
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg8, dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define dbg(...)
#endif
#pragma endregion debug
struct Line {
long long m, b;
Line(long long _m, long long _b) : m(_m), b(_b) {}
long long operator()(long long x) { return m * x + b; }
friend long double intersect(const Line &l1, const Line &l2) {
return (long double)(l2.b - l1.b) / (long double)(l1.m - l2.m);
}
friend ostream& operator<<(ostream &os, const Line &l) {
return os << '{' << l.m << "x + " << l.b << '}';
}
};
int main() {
int N, K;
cin >> N >> K;
vector<int> A(N + 1), P(N + 1, 0);
for (int i = 1; i <= N; i++) {
cin >> A[i];
P[i] = P[i - 1] + A[i];
}
vector<vector<long long>> dp(K + 2, vector<long long>(N + 1, 0));
vector<vector<int>> par(K + 2, vector<int>(N + 1, 0));
for (int k = 1; k <= K + 1; k++) {
deque<pair<Line, int>> dq;
for (int i = 1; i <= N; i++) {
Line l(P[i - 1], dp[k - 1][i - 1] - P[i - 1] * P[N]);
while (dq.size() >= 2 && intersect(l, dq[dq.size() - 2].first) < intersect(l, dq[dq.size() - 1].first))
dq.pop_back();
dq.emplace_back(move(l), i - 1);
while (dq.size() >= 2 && dq[0].first(P[i]) <= dq[1].first(P[i]))
dq.pop_front();
dp[k][i] = dq[0].first(P[i]) + P[i] * P[N] - P[i] * P[i];
par[k][i] = dq[0].second;
}
}
cout << dp[K + 1][N] << '\n';
vector<int> ans;
for (int k = K + 1, c = N; k > 0; k--) {
if (c != N)
ans.push_back(c);
c = par[k][c];
}
reverse(ans.begin(), ans.end());
for (int c : ans)
cout << c << ' ';
cout << '\n';
/*
cerr << "dp:\n";
for (int k = 1; k <= K + 1; k++) {
dbg(dp[k]);
}
cerr << "par:\n";
for (int k = 1; k <= K + 1; k++) {
dbg(par[k]);
}*/
}
