#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
ll P[maxn+1], dp[maxn+1][205];
int par[maxn+1][205], n, K, v[maxn+1];
void f(int l, int r, int tl, int tr, int j) {
if(l > r) return ;
int tm = (l + r) / 2, p = tl;
for(int i=tl; i<=min(tm, tr); i++) {
ll v = dp[i-1][j-1] + (P[tm] - P[i-1]) * (P[n] - P[tm]);
if(v > dp[tm][j]) {
dp[tm][j] = v;
par[tm][j] = i - 1;
p = i;
}
}
f(l, tm-1, tl, p, j);
f(tm+1, r, p, tr, j);
}
int main() {
cin >> n >> K;
for(int i=1; i<=n; i++) cin >> v[i];
for(int i=1; i<=n; i++) P[i] = P[i-1] + v[i];
for(int j=1; j<=K; j++) f(1, n, 1, n, j);
int pos = 0;
for(int i=1; i<n; i++)
if(dp[i][K] >= dp[pos][K]) pos = i;
cout << dp[pos][K] << '\n';
int curr = pos, k = K;
vector<int> ans;
while(k) {
ans.push_back(curr);
curr = par[curr][k];
if(k == 1) break;
k--;
}
reverse(ans.begin(), ans.end());
for(int &x : ans) cout << x << " ";
return 0;
}
