#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lf = long double;
#define x first
#define y second
struct Line{
ll a, b, i;
ll f(ll x){
return a * x + b;
}
};
lf X_cross(Line f, Line g){
return 1.0 * (f.b - g.b) / (g.a - f.a);
}
ll N, K;
ll A[100005];
ll S[100005];
ll D[2][100005];
int T[202][100002];
int main(){
cin.tie(0) -> sync_with_stdio(false);
cin >> N >> K;
for(int i = 1; i <= N; i++){
cin >> A[i];
S[i] = S[i - 1] + A[i];
}
for(int i = 1; i <= K; i++){
ll p = i % 2, q = (i - 1) % 2;
deque<Line> dq;
dq.push_back({S[i], D[q][i] - S[i] * S[i], i});
for(int j = i + 1; j <= N; j++){
while(dq.size() >= 2 && dq[0].f(S[j]) <= dq[1].f(S[j])) dq.pop_front();
D[p][j] = dq[0].f(S[j]);
T[i][j] = dq[0].i;
Line f = {S[j], D[q][j] - S[j] * S[j], j};
while(dq.size() >= 2 && X_cross(dq[dq.size() - 1], dq[dq.size() - 2]) >= X_cross(dq[dq.size() - 2], f)) dq.pop_back();
dq.push_back(f);
}
}
cout << D[K % 2][N] << '\n';
ll idx = N;
for(int i = K; i >= 1; i--){
idx = T[i][idx];
cout << idx << ' ';
}
}
