#include <bits/stdc++.h>
// #ifndef ONLINE_JUDGE
// #include <debug.h>
// #else
// #define debug(...)
// #endif
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
constexpr int MAX = 2e+5 + 1, INF = 2e+17, MOD = 1e+9 + 7, K = 31;
vector <int> pr;
vector <vector <int>> dp;
vector <vector <int32_t>> p;
int get(int l, int r) {
if (l > r) return 0;
return pr[r] - pr[l-1];
}
void solve(int k, int tl, int tr, int l, int r) {
if (tl > tr) return;
int tm = (tl + tr) / 2;
int ans = -INF, o = l;
for (int i = l; i <= min(r, tm); i++) {
int c = get(1, i-1) * get(i, tm) + dp[0][i-1];
if (c > ans) {
ans = c;
o = i;
}
}
dp[1][tm] = ans;
p[k][tm] = o;
if (tl == tr) return;
solve(k, tl, tm-1, l, o);
solve(k, tm+1, tr, o, r);
}
void _() {
int n, k;
cin >> n >> k;
vector <int> v(n+1, 0);
for (int i = 1; i <= n; i++) cin >> v[i];
pr = v;
for (int i = 1; i <= n; i++) pr[i] += pr[i-1];
dp.assign(2, vector <int>(n+1, -INF));
p.assign(k+1, vector <int32_t>(n+1, 0));
for (int i = 1; i <= n; i++) {
dp[0][i] = 0;
}
for (int i = 1; i <= k; i++) {
solve(i, 1, n,1, n);
dp[0].swap(dp[1]);
}
cout << dp[0][n] << endl;
int x = n, y = k;
vector <int> res;
while (y > 0) {
res.pb(p[y][x]);
x = p[y][x] - 1;
y--;
}
reverse(all(res));
for (int &i : res) cout << i-1 << ' ';
}
signed main() {
// freopen("sequence.in", "r", stdin);
// freopen("sequence.out", "w", stdout);
GOOD_LUCK
int tests=1;
// cin >> tests;
for (int i=1; i <= tests; i++) {
_();
cout << endl;
}
return 0;
}
