#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 1000'10;
vector<ll> dp[2];
ll pref[N];
ll arr[N];
int pre[N][210];
bool slope(ll a, ll b, ll c) {
return (((dp[0][a] - dp[0][b])*(-pref[c]+pref[b])) >= ((dp[0][b] - dp[0][c])*(-pref[b] + pref[a])));
/* slope(cur, dq[0]) >= slope(dq[0], dq[1])
*/
}
ll val(ll idx, ll x) {
return (-pref[idx]*x) + dp[0][idx];
}
int32_t main () {
ll n, k;
cin >> n >> k;
for(int i = 0;i<n;i++)
cin >> arr[i];
pref[0] = arr[0];
for(int i = 0;i<2;i++)dp[i].resize(n+1);
for(int i = 1;i<n;i++)pref[i] = pref[i-1]+arr[i];
if(n == 2) {
long long ans = arr[0] * arr[1];
cout << ans << "\n";
cout << 1 << "\n";
return 0;
}
for(int i= 0;i<=n;i++) {
for(int j = 0;j<=k+1;j++) {
pre[i][j] = -1;
}
}
deque<ll> dq;
for(int j = 1;j<=k;j++) {
dq.clear();
for(int i = 0;i<n;i++) {
ll cur = i, x = pref[n-1]-pref[i], ans = 0;
if(j > 1) {
while(dq.size() >= 2 && val(dq.back(), x) <=
val(dq[dq.size()-2], x))dq.pop_back();
}
if(dq.size()){
int z = dq.back();
ans = dp[0][z] + (pref[i]-pref[z])*(pref[n-1]-pref[i]);
pre[i][j] = dq.back();
}
else {
ans = pref[i]*(pref[n-1]-pref[i]);
pre[i][j] = -1;
}
dp[1][i] = ans;
if(j > 1 and i!=n-2) {
while(dq.size() >= 2 && slope(cur, dq[0], dq[1]))dq.pop_front();
dq.push_front(cur);
}
// cout << dp[1][i] << " ";
}
// cout << "\n";
dp[0].swap(dp[1]);
}
ll mx = -1, idx = -1;
for(int i = 0;i<n;i++) {
if(dp[0][i] >= mx) {
mx = dp[0][i];
idx = i;
}
}
cout << mx << "\n";
while(idx!=-1 and k > 0) {
cout << idx+1 << " ";
idx = pre[idx][k];
k--;
}
cout << "\n";
}
