#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
// #pragma GCC optimize("O3", "unroll-loops")
// #pragma GCC target("avx2", "popcnt")
using namespace std;
ll divide(ll a, ll b){
if (b == 0){
if (a > 0){
return 1e18;
}
if (a < 0){
return -1e18;
}
return 0;
}
ll d = 0;
if (a % b){
d = 1;
}
if ((a > 0 && b > 0) || (a < 0 && b < 0)){
return (a / b) + d;
}
return -(abs(a) / abs(b));
}
struct Line{
ll k = 0, b = -1e18, id = -1;
Line(ll k, ll b, ll id) : k(k), b(b), id(id){}
ll operator()(ll x){
return k * x + b;
}
ll isect(const Line& a){
return divide(a.b - b, k - a.k);
}
};
struct LiChao{
int sz;
vector<Line> tree;
vector<ll> uniq;
LiChao(vector<ll> a){
int n = a.size();
sz = 1;
while (sz < 2 * n){
sz *= 2;
}
tree.resize(sz, {0, -(ll)1e18, -1});
uniq = a;
assert(is_sorted(all(a)));
uniq.erase(unique(all(uniq)), uniq.end());
while (uniq.size() < sz / 2){
uniq.push_back(uniq.back() + 1);
}
}
void clear(){
for (int v = 0; v < sz; v++){
tree[v].k = 0;
tree[v].b = -1e18;
tree[v].id = -1;
}
}
void insert(int v, int tl, int tr, Line q){
int tm = (tl + tr) / 2;
bool l = (tree[v](uniq[tl]) < q(uniq[tl]));
bool m = (tree[v](uniq[tm]) < q(uniq[tm]));
if (m){
swap(tree[v], q);
}
if (tl == tm){
return;
}
if (l == m){
insert(v * 2 + 1, tm + 1, tr, q);
} else {
insert(v * 2, tl, tm, q);
}
}
void insert(Line q){
insert(1, 0, sz / 2 - 1, q);
}
pair<ll, ll> get(int v, int tl, int tr, ll x){
if (tl == tr){
return {tree[v](x), tree[v].id};
}
int tm = (tl + tr) / 2;
if (x <= uniq[tm]){
return max(pair<ll, ll>{tree[v](x), tree[v].id}, get(v * 2, tl, tm, x));
} else {
return max(pair<ll, ll>{tree[v](x), tree[v].id}, get(v * 2 + 1, tm + 1, tr, x));
}
}
pair<ll, ll> get(ll x){
return get(1, 0, sz / 2 - 1, x);
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef ON_PC
freopen("input.txt", "r", stdin);
#endif
// freopen("output.txt", "w", stdout);
int T = 1;
// cin >> T;
while (T--){
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
vector<ll> pref(n + 1);
for (int i = 1; i <= n; i++){
pref[i] = pref[i - 1] + a[i];
}
vector<ll> dp0(n + 1);
vector<ll> dp1(n + 1, -1e18);
vector<vector<int>> p(n + 1, vector<int>(k + 1));
vector<Line> st;
vector<double> from;
for (int cnt = 1; cnt <= k; cnt++){
st.clear();
from.clear();
dp1.assign(n + 1, -1e18);
int pos = 0;
for (int i = 1; i <= n; i++){
if (!st.empty()){
if (pos >= st.size()){
pos = st.size() - 1;
}
while (pos < from.size() && from[pos] < pref[i - 1]){
pos++;
}
Line l = st[pos - 1];
int j = l.id;
ll val = l(pref[i - 1]);
dp1[i] = -(pref[i - 1] * pref[i - 1]) + pref[n] * pref[i - 1] + val;
p[i][cnt] = j;
}
if (dp0[i] != -1e18){
Line l = {pref[i - 1], dp0[i] - pref[n] * pref[i - 1], i};
while (st.size() > 1 && l.isect(st.back()) < st.back().isect(st[st.size() - 2])){
st.pop_back();
from.pop_back();
}
st.push_back(l);
if (st.size() == 1){
from.push_back(-1e9);
} else {
from.push_back(l.isect(st[st.size() - 2]));
}
}
// for (int j = i - 1; j >= 1; j--){
// if (dp[j][cnt - 1] != -1e18 &&
// dp[j][cnt - 1] + (pref[n] - pref[i - 1]) * 1ll * (pref[i - 1] - pref[j - 1]) >= dp[i][cnt]){
// p[i][cnt] = j;
// dp[i][cnt] = max(dp[i][cnt], dp[j][cnt - 1] + (pref[n] - pref[i - 1]) * 1ll * (pref[i - 1] - pref[j - 1]));
// }
// }
}
dp0.swap(dp1);
}
int v = 1;
for (int i = 1; i <= n; i++){
if (dp0[i] > dp0[v]){
v = i;
}
}
cout << dp0[v] << "\n";
vector<int> res;
for (int cnt = k; cnt >= 1; cnt--){
res.push_back(v);
v = p[v][cnt];
}
reverse(all(res));
for (int i = 0; i < k; i++){
cout << res[i] - 1 << " ";
}
cout << "\n";
// cout << dp[1][n][k] << "\n";
// vector<int> res;
// queue<array<int, 3>> q;
// q.push({1, n, k});
// while (!q.empty()){
// array<int, 3> t = q.front();
// q.pop();
// pair<int, int> w = p[t[0]][t[1]][t[2]];
// res.push_back(w.first);
// if (t[2]){
// q.push({t[0], w.first, w.second});
// q.push({w.first + 1, t[1], t[2] - 1 - w.second});
// }
// }
// assert(!res.empty());
// sort(all(res));
// for (int i = 0; i < res.size(); i++){
// if (res[i]){
// cout << res[i] << " ";
// }
// }
// cout << "\n";
}
return 0;
}
