#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<long long,long long>
#define fi first
#define se second
const int N = 1e5+5;
int n,k,a[N],trace[N][201];
long long dp[N],pref[N],suf[N],pre[N];
struct line{
int id;
long long a,b;
};
bool bad(const line &l1, const line &l2, const line &l3){
__int128 left = (__int128)(l2.b-l1.b)*(__int128)(l2.a-l3.a);
__int128 right = (__int128)(l3.b-l2.b)*(__int128)(l1.a-l2.a);
return left >= right;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
pref[i] = pref[i-1]+a[i];
}
for(int i = n; i >= 1; i--) suf[i] = suf[i+1]+a[i];
for(int j = 1; j <= k; j++){
deque<line>dq;
dq.push_back({0,0,0});
for(int i = 1; i <= n; i++){
while(dq.size() >= 2 && -suf[i+1]*dq[0].a+dq[0].b <= -suf[i+1]*dq[1].a+dq[1].b) dq.pop_front();
if(i >= j){
if(dq.empty()) dp[i] = suf[i+1]*pref[i];
else{
dp[i] = -suf[i+1]*(dq[0].a-pref[i])+dq[0].b;
trace[i][j] = dq[0].id;
}
}
if(i >= j-1){
line nw = {i,pref[i],pre[i]};
while(dq.size() >= 2 && bad(dq[dq.size()-2],dq[dq.size()-1],nw)) dq.pop_back();
dq.push_back(nw);
}
}
for(int i = 1; i <= n; i++){
if(i < j) pre[i] = 0;
else pre[i] = dp[i];
}
}
long long ans = -1;
int idx;
for(int i = k; i <= n; i++){
if(ans < dp[i]){
ans = dp[i];
idx = i;
}
}
cout << ans << "\n";
vector<int>res;
while(k > 0){
res.push_back(idx);
idx = trace[idx][k];
k--;
}
for(int i = res.size()-1; i >= 0; i--) cout << res[i] << " ";
}
