#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int, int>
using namespace std;
const int mod = 1e9 + 7;
const int inf = 1e18;
int LR = 5e12 + 5;
const int N = 1e5 + 5;
const int K = 2e2 + 5;
int n, k, a[N], pref[N], dp[2][N];
int32_t pos[K][N];
struct line {
int m, c, idx;
line(int mm, int cc, int idxx) : m(mm), c(cc), idx(idxx) {}
int cal(int x){
return m * x + c;
}
long double findx(line cur){
return (long double)(c - cur.c) / (cur.m - m);
}
};
struct convexhull {
deque <line> dq;
void update(line cur){
while (dq.size() > 1 && cur.findx(dq[0]) <= cur.findx(dq[1])) dq.pop_front();
dq.emb(cur);
}
pii query(int val){
while (dq.size() > 1 && dq[dq.size() - 1].cal(val) <= dq[dq.size() - 2].cal(val)) dq.pop_back();
return {dq.back().cal(val), dq.back().idx};
}
} hull;
signed main(){
cin.tie(NULL)->sync_with_stdio(false);
cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i], pref[i] = pref[i - 1] + a[i];
LR = pref[n];
for (int i = 1; i <= n; i++) dp[0][i] = -inf;
dp[0][0] = 0;
for (int i = 1; i <= k; i++) {
dp[i % 2][0] = -inf;
hull.dq.clear();
hull.update(line(-pref[0], dp[(i - 1) % 2][0], 0));
for (int j = 1; j < n; j++) {
pii curr = hull.query(pref[n] - pref[j]);
curr.first += pref[j] * pref[n] - pref[j] * pref[j];
dp[i % 2][j] = curr.first;
pos[i][j] = curr.second;
hull.update(line(-pref[j], dp[(i - 1) % 2][j], j));
// cout << i << ", " << j << " : " << dp[i][j] << ", " << pos[i][j] << "\n";
}
}
int ans = -inf, idx = 0, curk = k;
for (int i = 1; i < n; i++) {
if (dp[k % 2][i] >= ans) ans = dp[k % 2][i], idx = i;
}
cout << ans << "\n";
if (ans == 0) {
for (int i = 1; i <= k; i++) cout << i << " ";
}
else {
while (curk > 0) {
cout << idx << " ";
idx = pos[curk--][idx];
}
}
}
/*
*ORDER OF SPLIT DOESN'T MATTER*
dp[i][j] = max score after splitting i'th round at after position j
dp[i][j] = max(dp[i - 1][k] + (pref[j] - pref[k]) * (pref[n] - pref[j]))
dp[i][j] = max(dp[i - 1][k] + pref[j] * pref[n] - pref[j]^2 - pref[k] * pref[n] + pref[k] * pref[j])
dp[i][j] = pref[j] * pref[n] - pref[j]^2 + max(dp[i - 1][k] - pref[k] * (pref[n] - pref[j]))
const = pref[j] * pref[n] - pref[j]^2
m = -pref[k]
x = pref[n] - pref[j]
c = dp[i - 1][k]
*/
