#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
#define kien long long
#define int long long
#define pb push_back
#define FOR(i, a, b) for (int i = a;i <= b; i++)
#define FORD(i, a, b) for (int i = a;i >= b; i--)
#define pii pair<long long, int>
#define fi first
#define se second
#define dembit(a) __builtin_popcountll(a)
//#define task "kien"
//#define fin(x) freopen(x".inp","r",stdin)
//#define fou(x) freopen(x".out","w",stdout)
//#define debug(x) cout << x << " ";
//#define down cout << "\n"
//const kien mod = 1e9 + 7;
//const int NTEST = 100;
//const int Million = 1e6 + 5;
const int mxn = 1e5 + 1;
mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
kien rand(kien l, kien r) {
assert(l <= r);
return uniform_int_distribution<kien>(l, r)(rd);
}
kien n, k, m, dem, suf[mxn], u, v, a[mxn];
kien vtr, dp[mxn][2], trace[205][mxn];
void dnc (int id, int l, int r, int lo, int hi) {
if (l > r) return;
int mid = (l + r) >> 1;
pii kq = {-1e18, -1};
for (int i = lo; i <= min(mid, hi); i++) {
if (kq.fi <= dp[i - 1][0] + suf[mid + 1] * (suf[i] - suf[mid + 1])) { kq.fi = dp[i - 1][0] + suf[mid + 1] * (suf[i] - suf[mid + 1]); kq.se = i; }
}
dp[mid][1] = kq.fi;
trace[id][mid] = kq.se - 1;
dnc(id, l, mid - 1, lo, kq.se);
dnc(id, mid + 1, r, kq.se, hi);
}
void solve() {
cin >> n >> k;
FOR (i, 1, n) cin >> a[i];
FORD (i, n, 1) suf[i] = suf[i + 1] + a[i];
FOR (i, 1, k) {
dnc(i, i, n - 1, i, n - 1);
/// vì một trong hai phía không được rỗng !!!
FOR (j, i, n) dp[j][0] = dp[j][1];
}
pii res = {0, 0};
vector <int> vec;
for (int i = k; i < n; i++) if (res.fi <= dp[i][1]) res = {dp[i][1], i};
// for (int i = k; i <= n; i++) cout << dp[i][1] << " ";
for (int i = k; i > 0; i--) {
vec.pb(res.se);
res.se = trace[i][res.se];
}
reverse(vec.begin(), vec.end());
cout << res.fi << "\n";
for (auto x : vec) cout << x << " ";
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
//
// if (fopen(task".inp", "r")) {
// fin(task); fou(task);
// }
solve();
cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}
