#include <bits/stdc++.h>
#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair
using namespace std;
typedef long long ll;
const ll inf = (ll)1e9 + 7;
const int N = (int)1e5 + 2;
int n,k,id;
int pr[N][201];
ll a[N],p[N];
ll dp[N][2];
ll mx;
ll calc (int r,int l) {
return (p[r] - p[l]) * 1ll * (p[n] - p[r]);
}
void compute (int k,int l,int r,int L,int R) {
if (l > r)
return;
int m = (l + r) >> 1;
int opt = -1;
for (int i = L; i <= min(m,R); i ++) {
ll now = dp[i - 1][(k - 1) % 2] + calc(m,i - 1);
if (now > dp[m][k % 2])
dp[m][k % 2] = now,opt = i;
}
pr[m][k] = opt;
compute (k,l,m - 1,L,opt);
compute (k,m + 1,r,opt,R);
}
int main () {
cin >> n >> k;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
p[i] = p[i - 1] + a[i];
}
for (int i = 1; i <= n; i ++) {
dp[i][1] = calc(i,0);
pr[i][1] = 1;
}
for (int i = 2; i <= k; i ++)
compute (i,i,n,i,n);
for (int i = 1; i <= n; i ++) {
if (mx < dp[i][k % 2])
mx = max(mx,dp[i][k % 2]),id = i;
}
cout << mx << endl;
deque<int> dq;
while (id > 0 && k > 0) {
dq.push_front(id);
id = pr[id][k] - 1;
k --;
}
for (int i = 0; i < (int)dq.size(); i ++)
cout << dq[i] << " ";
}
/**
7 3
4 1 3 4 0 2 3
**/
