/*
* File created on 01/08/2022 at 17:20:18.
* Link to problem:
* Description:
* Time complexity: O()
* Space complexity: O()
* Status: ---
* Copyright: Ⓒ 2022 Francois Vogel
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace std;
using namespace __gnu_pbds;
#define mp pair<pii, int>
#define pii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define size(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear
#define int ll
#define ll long long
#define ld long double
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e18;
ld xIntersection(int a1, int b1, int a2, int b2) {
return (ld)(b1-b2)/(ld)(a2-a1);
}
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, kConst;
cin >> n >> kConst;
int b [n];
for (int i = 0; i < n; i++) cin >> b[i];
int p [n];
p[0] = b[0];
for (int i = 1; i < n; i++) p[i] = p[i-1]+b[i];
int sum = p[n-1];
int pdp [n+1];
int ndp [n+1];
for (int i = 0; i < n; i++) pdp[i] = -inf;
pdp[n] = 0;
signed to [kConst+1][n];
for (int i = 0; i <= kConst; i++) {
deque<mp> q;
for (int j = n-1; j >= 0; j--) {
int slope = 2*p[j];
int xint = p[j]*sum-p[j]*p[j]+pdp[j+1];
while (size(q) >= 2 && xIntersection(q[0].f.f, q[0].f.s, q[1].f.f, q[1].f.s) <= xIntersection(q[1].f.f, q[1].f.s, slope, xint)) {
q.pop_front();
}
q.push_front(mp(pii(slope, xint), j+1));
int query = 0;
if (j) query = p[j-1];
while (size(q) >= 2 && q[size(q)-2].f.f*query+q[size(q)-2].f.s >= q.back().f.f*query+q.back().f.s) {
q.pop_back();
}
to[i][j] = q.back().s;
ndp[j] = q.back().f.f*query+q.back().f.s;
if (j) ndp[j] -= p[j-1]*sum+p[j-1]*p[j-1];
}
for (int j = 0; j < n; j++) pdp[j] = ndp[j];
pdp[n] = -inf;
}
cout << pdp[0]/2 << '\n';
vi res;
int x = 0;
for (int i = kConst; i > 0; i--) {
x = to[i][x];
res.pb(x);
}
for (int i : res) cout << i << ' ';
cout.flush();
int d = 0;
d++;
}
