#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;
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;
}
};
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;
// }
sz = 4 * n;
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 / 4 - 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 / 4 - 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));
LiChao st(pref);
for (int cnt = 1; cnt <= k; cnt++){
// st.clear();
dp1.assign(n + 1, -1e18);
for (int i = 1; i <= n; i++){
pair<ll, ll> t = st.get(pref[i - 1]);
if (t.second != -1){
dp1[i] = -(pref[i - 1] * pref[i - 1]) + pref[n] * pref[i - 1] + t.first;
p[i][cnt] = t.second;
}
if (dp0[i] != -1e18){
st.insert({pref[i - 1], dp0[i] - pref[n] * pref[i - 1], i});
}
// 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;
}
