#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e18;
struct line {
int m, c, id;
int operator[](int x) {
return m*x+c;
}
};
struct cht {
deque<line> dq;
int query(int x) {
while (dq.size()>1 && dq[1][x]>dq[0][x]) dq.pop_front();
return dq.front()[x];
}
void add(line l) {
int n=dq.size();
while (dq.size()>1 && (l.c-dq[n-2].c)*(dq[n-2].m-dq[n-1].m)<=(dq[n-1].c-dq[n-2].c)*(dq[n-2].m-l.m)) {
n--; dq.pop_back();
} dq.push_back(l);
}
void clear() {
dq.clear();
dq.push_back({0, 0, 0});
}
};
signed main() {
cin.tie(0)->sync_with_stdio(false);
int n, k;
cin >> n >> k;
vector<int> pre(n+1, 0);
for (int i = 1; i <= n; ++i) {
cin >> pre[i];
pre[i]+=pre[i-1];
}
cht lines;
vector<vector<int>> dp(n+1, vector<int>(2, 0)), prev(n+1, vector<int>(k+1, 0));
for (int j = 1; j <= k; ++j) {
lines.clear();
for (int i = 1; i <= n; ++i) {
dp[i][j%2]=pre[i]*(pre[n]-pre[i])+lines.query(pre[i]);
prev[i][j]=lines.dq.front().id;
lines.add({pre[i], dp[i][(j-1)%2]-pre[n]*pre[i], i});
}
}
int m=0, j=0;
for (int i = 1; i <= n; ++i) {
if (dp[i][j%2]>m) m=dp[i][k%2], j=i;
} cout << m << '\n';
cout << j;
for (int i = 0; i < k-1; ++i) {
j=prev[j][k-i];
cout << ' ' << j;
} cout << '\n';
return 0;
}
