#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ii> vii;
typedef set<ii> sii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define float long double
deque<iii> dq;
int ufds[100005];
int find_set(int x) {
//printf("Finding set for %d\n", x);
return ufds[x] = ((ufds[x] == x) ? x : find_set(ufds[x]));
}
void merge_set(int x, int y) {
ufds[find_set(x)] = ufds[find_set(y)];
}
int f(ii line, int x) {
return line.fi * x + line.se;
}
ii query(int x) {
while(dq.size() > 1) {
if(f(dq[0].fi, x) < f(dq[1].fi, x)) dq.pop_front();
else break;
}
return mp(f(dq[0].fi, x),dq[0].se);
}
float intersect(int a, int b, int c, int d) {
return (float)(d - b) / (a - c);
}
float intersect(ii p1, ii p2) {
return intersect(p1.fi, p1.se, p2.fi, p2.se);
}
void ins(int m, int c, int idx) {
ii line = ii(m, c);
while(dq.size() > 1) {
int s = dq.size();
if(intersect(dq[s - 1].fi, line) <= intersect(dq[s - 2].fi, line)) dq.pop_back();
else break;
}
dq.push_back(mp(line,idx));
}
int32_t main() {
int n, k; cin >> n >> k; int x[n + 1]; x[0] = 0;
REP(i, 1, n + 1) {
cin >> x[i];
x[i] += x[i - 1];
}
pair<int,int> dp[n + 1][k + 1];
REP(i, 0, n + 1) dp[i][0] = mp(0,0);
REP(i, 1, k + 1) dp[0][i] = mp(0,0);
REP(j, 1, k + 1) {
while(!dq.empty()) dq.pop_back();
ins(0, 0, 0);
REP(i, 1, n + 1) {
dp[i][j] = query(x[i]);
ins(x[i], dp[i][j - 1].fi - x[i] * x[i], i);
//printf("Pushed back %d %d into convex hull\n", x[i], dp[i][j - 1].fi - x[i] * x[i]);
}
}
cout << dp[n][k].fi << "\n";
vector<int> v; int cur = n;
for(int i = k; i > 0; i--) {
v.pb(dp[cur][i].se);
cur = dp[cur][i].se;
}
REP(i, 0, v.size()) {
if(v[i] > 0) {
cout << v[i] << " ";
ufds[v.back()] = v[i];
if(ufds[v[i] + 1]) merge_set(v[i], v[i] + 1);
if(ufds[v[i] - 1]) merge_set(v[i] - 1, v[i]);
} else {
int x = find_set(1);
cout << x + 1 << " ";
if(x == 0) {
ufds[0] = 1;
ufds[1] = 1;
} else {
if(!ufds[x + 1]) ufds[x + 1] = x + 1;
merge_set(x, x + 1);
}
}
}
}
