#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#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 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() {
speed;
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[k + 1][n + 1];
REP(i, 0, n + 1) dp[0][i] = mp(0,0);
REP(i, 1, k + 1) dp[i][0] = mp(0,0);
REP(j, 1, k + 1) {
while(!dq.empty()) dq.pop_back();
ins(0, 0, 0);
REP(i, 1, n + 1) {
dp[j][i] = query(x[i]);
ins(x[i], dp[j - 1][i].fi - x[i] * x[i], i);
}
}
cout << dp[k][n].fi << "\n"; int cur = n;
for(int i = k; i > 0; i--) {
cout << dp[i][cur].se << " ";
cur = dp[i][cur].se;
}
}
