#include <bits/stdc++.h>
using namespace std;
namespace
{
template <typename T>
T fl_div(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
} // namespace
struct Line
{
long m, c;
int id;
long operator()(long x) const { return m * x + c; }
};
long isect(const Line &l1, const Line &l2) { return fl_div(l1.c - l2.c, l2.m - l1.m); }
void solve()
{
int n, k;
cin >> n >> k, ++k;
vector<long> a(n);
for (long &x : a)
cin >> x;
vector<long> pref(n + 1);
for (int i = 0; i < n; i++)
pref[i + 1] = pref[i] + a[i];
vector prv(n + 1, vector(k + 1, -1));
vector<deque<Line>> dp(k + 1);
dp[0].push_back({0, 0, 0});
for (int i = 0; i < n; i++)
{
for (int j = 0; j < min(k, i + 1); j++)
{
while ((int)dp[j].size() >= 2 && dp[j][1](pref[i + 1]) > dp[j][0](pref[i + 1]))
dp[j].pop_front();
prv[i + 1][j + 1] = dp[j][0].id;
Line line = {pref[i + 1], dp[j][0](pref[i + 1]) - pref[i + 1] * pref[i + 1], i + 1};
while ((int)dp[j + 1].size() >= 2 && line.m != dp[j + 1].back().m && isect(line, dp[j + 1].back()) <= isect(dp[j + 1].back(), dp[j + 1].end()[-2]))
dp[j + 1].pop_back();
if (dp[j + 1].empty() || line.m != dp[j + 1].back().m)
dp[j + 1].push_back(line);
}
}
long res = dp[k].back().c + pref[n] * pref[n];
vector<int> pos;
for (int i = prv[n][k], j = k; i > 0; i = prv[i][--j])
pos.push_back(i);
reverse(pos.begin(), pos.end());
cout << res << '\n';
for (int i : pos)
cout << i << ' ';
cout << '\n';
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(NULL);
solve();
return 0;
}
