#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
const int MAX_N = 1e5 + 10;
const int MAX_K = 2e2 + 10;
const long long INF = 9e18 + 7;
bool QueryMode;
int A[MAX_N];
int parent[MAX_K][MAX_N];
long long pre[MAX_N], dp[MAX_N];
class Line {
public :
mutable long long m, c, p;
mutable int idx;
Line() : m(0), c(-INF), p(0), idx(0) {}
Line(const long long &m_, const long long &c_, const int &i) : m(m_), c(c_), p(0), idx(i) {}
Line(const long long &m_, const long long &c_, const int &i, const long long &p_) : m(m_), c(c_), idx(i), p(p_) {}
bool operator<(const Line &o) const {
if(QueryMode == true) {
return p < o.p;
}
return m < o.m;
}
};
class LineContainer : multiset <Line> {
public :
void init() {
clear();
}
long long divide(const long long &a, const long long &b) {
return a / b - ((a ^ b) < 0 and a % b != 0);
}
bool intersect(iterator now, iterator nxt) {
if(nxt == end()) {
now->p = INF;
return false;
}
if(now->m == nxt->m) {
now->p = INF;
if(now->c < nxt->c) {
now->p = -INF;
}
}
else {
now->p = divide(nxt->c - now->c, now->m - nxt->m);
}
return now->p >= nxt->p;
}
void addline(const Line &f) {
auto nxt = insert(f), now = nxt++, prv = now;
while(intersect(now, nxt) == true) {
nxt = erase(nxt);
}
if(prv != begin() and intersect(--prv, now) == true) {
intersect(prv, now = erase(now));
}
while((now = prv) != begin() and (--prv)->p >= now->p) {
intersect(prv, erase(now));
}
}
pair <long long, int> query(const long long &x) {
if(empty()) {
return make_pair(-INF, -1);
}
QueryMode = true;
auto it = *lower_bound(Line(-INF, -INF, 0, x));
QueryMode = false;
return make_pair(it.m * x + it.c, it.idx);
}
}cht;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, K;
cin >> N >> K;
for(int i = 1; i <= N; i++) {
cin >> A[i];
pre[i] = pre[i - 1] + A[i];
}
for(int i = 1; i < N; i++) {
dp[i] = (pre[N] - pre[i]) * pre[i];
cht.addline(Line(pre[i], -pre[i] * pre[N] + dp[i], i));
}
for(int i = 2; i <= K; i++) {
for(int j = i; j < N; j++) {
auto [res, idx] = cht.query(pre[j]);
dp[j] = res + pre[j] * pre[N] - pre[j] * pre[j];
parent[i][j] = idx;
}
cht.init();
for(int j = i; j <= N; j++) {
cht.addline(Line(pre[j], -pre[j] * pre[N] + dp[j], j));
}
}
long long ans = -INF;
int pos = N;
for(int i = K; i < N; i++) {
if(ans < dp[i]) {
ans = dp[i];
pos = i;
}
}
stack <int> stk;
while(K > 0) {
stk.emplace(pos);
pos = parent[K--][pos];
}
cout << ans << '\n';
while(!stk.empty()) {
cout << stk.top() << ' ';
stk.pop();
}
return 0;
}
