#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;
template<class A, class B>
bool maximize(A& x, B y) {
if (x <= y) return x = y, true; else return false;
}
template<class A, class B>
bool minimize(A& x, B y) {
if (x > y) return x = y, true; else return false;
}
/* END OF TEMPLATE */
const int N = 100007;
int n, k, a[N];
ll pre[N];
ll f[N], g[N];
int trace[207][N];
struct Line {
ll a, b, id;
Line() {
a = b = 0;
id = 0;
}
Line(ll a, ll b, int id) : a(a), b(b), id(id) {}
ll GetVal(ll x) {
return a * x + b;
}
};
// chu y trung` ho he so goc
vector<pair<Line, long double>> E;
long double GetIntersection(Line x, Line y) {
return (long double)(y.b - x.b) / (x.a - y.a);
}
void addLine(Line x) {
int n = E.size();
while (n > 1 && GetIntersection(x, E[n - 2].X) <= GetIntersection(E[n - 2].X, E[n - 1].X)) {
n--;
E.pop_back();
}
if (n == 0) E.push_back({x, -1e18}); else E.push_back({x, GetIntersection(x, E[n - 1].X)});
}
int idxE = 0;
pair<ll, int> GetMin(int x) {
if (E.empty()) return {-1e18, -1};
minimize(idxE, (int)E.size() - 1);
while (idxE + 1 < (int)E.size() && E[idxE + 1].Y <= x) idxE++;
int res = idxE;
return {E[res].X.GetVal(x), E[res].X.id};
}
int main() {
// freopen("TEST.INP", "r", stdin);
// freopen("TEST.OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
FOR(i, 1, n) cin>>a[i], pre[i] = pre[i - 1] + a[i];
FOR(i, 0, n) g[i] = f[i] = -1e18;
g[0] = 0;
FOR(num, 1, k + 1) {
idxE = 0;
E.clear();
int i = 1;
ll Max0 = g[0], idxMax0 = 0;
while (i <= n) {
if (pre[i] == 0) {
f[i] = Max0;
if (g[i] != -1e18 && maximize(Max0, g[i])) idxMax0 = i + 1;
i++;
continue;
}
else {
if (num == 1) {
f[i] = Max0;
trace[num][i] = 1;
}
int j = i;
while (j < n && pre[j] == pre[j + 1]) j++;
ll Max = -1e18, idx = 0;
// cout<<num<<" "<<i<<" "<<j<<"\n";
FOR(k, i, j) {
pair<ll, int> val = GetMin(pre[k]);
f[k] = val.X;
trace[num][k] = val.Y;
if (Max != -1e18 && maximize(f[k], Max + SQR(pre[k]))) trace[num][k] = idx + 1;
if (Max0 > -1e18 && maximize(f[k], Max0)) trace[num][k] = idxMax0;
if (g[k] != -1e18 && maximize(Max, g[k] - SQR(pre[k]))) idx = k;
}
if (Max != -1e18) addLine(Line(pre[idx], Max, idx + 1));
i = j + 1;
}
}
FOR(i, 0, n) g[i] = f[i], f[i] = -1e18;
// FOR(i, 1, n) {
// FORD(j, i, 1)
// if (dp[num - 1][j - 1] != -1e18)
// if (maximize(dp[num][i], 1LL * (pre[i] - pre[j - 1]) * pre[j - 1] + dp[num - 1][j - 1])) trace[num][i] = j;
// }
}
cout<<g[n]<<"\n";
vector<int> res;
k++;
while (trace[k][n] > 1 && k > 0) {
res.push_back(trace[k][n] - 1);
n = trace[k][n] - 1;
k--;
}
reverse(all(res));
for (auto x : res) cout<<x<<" ";
return 0;
}
