#include <bits/stdc++.h>
#define hash _hash_
#define y1 _y1_
#define dec _dec_
using namespace std;
using ll = long long;
using ull = unsigned long long;
const ll MOD = 1e9 + 7;
const ll oo = 1e18;
/*------------- I alone decide my fate ! -------------*/
/* Chiec den ong sao, sao 5 canh tuoi mau... */
int N, K, a[100009];
ll dp[209][205], pre[100009];
int par[209][205];
// Convex Hull Trick - maximum
struct Line {
ll m, b; // y = m*x + b
int idx; // lưu vị trí k
long double interX(const Line &other) const {
return (long double)(other.b - b) / (m - other.m);
}
};
struct CHT {
deque<Line> dq;
void add(ll m, ll b, int idx) {
Line l = {m,b,idx};
while(dq.size() >= 2) {
auto &l1 = dq[dq.size()-2], &l2 = dq.back();
if ((l2.b - l1.b) * (l1.m - l.m) >= (l.b - l1.b) * (l1.m - l2.m)) dq.pop_back();
else break;
}
dq.push_back(l);
}
pair<ll,int> query(ll x) {
while(dq.size() >= 2) {
auto &l1 = dq[0], &l2 = dq[1];
if (l2.m * x + l2.b >= l1.m * x + l1.b) dq.pop_front();
else break;
}
return {dq[0].m * x + dq[0].b, dq[0].idx};
}
};
void solve() {
cin >> N >> K;
for (int i = 1; i <= N; i ++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
for (int i = 0; i < 209; ++i)
for (int j = 0; j < 205; ++j)
par[i][j] = -1;
for(int j = 1; j <= K; j++) {
dp[0][j] = -oo;
}
dp[0][0] = 0;
for(int j = 1; j <= K; j++) {
CHT cht;
cht.add(0, 0, 0); // k=0
for(int i = 1; i <= N; i++) {
auto [val, k] = cht.query(pre[i]);
dp[i][j] = val;
par[i][j] = k;
// thêm dòng mới: y = pre[k]*x + (dp[k][j-1]-pre[k]^2)
cht.add(pre[i], dp[i][j-1]-pre[i]*pre[i], i);
}
}
cout << dp[N][K] << "\n";
vector<int> cuts;
int ci = N, cj = K;
while(cj > 0) {
int t = par[ci][cj];
if (t == -1) break;
if (t > 0) cuts.push_back(t);
ci = t;
--cj;
}
reverse(cuts.begin(), cuts.end());
for(size_t i=0;i<cuts.size();i++){
if(i) cout<<" ";
cout<<cuts[i];
}
cout<<"\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
solve();
}
