#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <LL, LL> PLL;
constexpr int NMAX = 1e5 + 5;
constexpr LL INF = 1LL * 1e18;
constexpr int KMAX = 205;
int N, K;
LL dp[NMAX][2];
LL sp[NMAX];
void Read () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
for (int i = 1; i <= N; ++ i ) {
int x;
cin >> x;
sp[i] = sp[i-1] + 1LL * x;
}
}
int Q[NMAX];
int bef[NMAX][KMAX];
int vf =0 ;
PLL Slope (int ind, int when) {
return {sp[ind], dp[ind][((when-1)&1)] - sp[ind] * sp[N]};
}
double Intersect (PLL a, PLL b) {
double numar = (1.0 * a.second - 1.0 * b.second);
double numi = (1.0 * b.first - 1.0 * a.first);
return (numar/numi);
}
void CautBinar (LL coord, int ind, int what) {
int st = 1, dr = vf;
int ans = 1;
while (st <= dr) {
int mij = (st + dr) / 2;
pair <double, double> interval;
if (mij == 1) interval.first = -INF;
else interval.first = Intersect(Slope(Q[mij-1], what), Slope(Q[mij], what));
if (mij == vf) interval.second = INF;
else interval.second = Intersect(Slope(Q[mij], what), Slope(Q[mij+1], what));
if (interval.second < coord) st = mij + 1;
else if (interval.first > coord) dr = mij - 1;
else {
ans = mij;
break;
}
}
PLL slope = Slope(Q[ans], what);
dp[ind][(what&1)] = sp[ind] * (sp[N] - sp[ind]) + slope.first * coord + slope.second;
bef[ind][what] = Q[ans];
}
void Solve () {
for (int j = 1; j <= K; ++ j ) {
vf = 1;
Q[1] = j-1;
for (int i = j; i <= N; ++ i ) {
CautBinar(sp[i], i, j);
while (vf > 1 && Intersect(Slope(Q[vf-1], j), Slope(Q[vf], j)) >= Intersect(Slope(Q[vf], j), Slope(i, j)) )
-- vf;
Q[++vf] = i;
}
}
int index = 0;
LL ans = 0;
for (int i = K; i <= N; ++ i ) {
LL val = dp[i][(K&1)];
if (val > ans) {
ans = val;
index = i;
}
}
cout << ans << '\n';
cout << index << " ";
for (int i = K-1; i >= 1; -- i ) {
index = bef[index][i+1];
cout << index << " ";
}
}
int main () {
Read();
Solve();
return 0;
}
