#include "bits/stdc++.h"
using namespace std;
#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif
#define ll long long
const int N=1e5+5;
const int mod=1e9+7;
int n,k,a[N],op[205][N],p[N];
ll dp[2][N];
void dnc(int j, int l, int r, int optl, int optr){
if(l>r) return;
int mid=(l+r)>>1;
pair <ll,int> opt={0,0};
for(int x=min(mid,optr); x>=optl; x--) opt=max(opt,{dp[(j&1)^1][x-1]+1ll*(p[mid]-p[x-1])*(p[n]-p[mid]),x});
dp[j&1][mid]=opt.first;
op[j][mid]=opt.second;
dnc(j,l,mid-1,optl,opt.second);
dnc(j,mid+1,r,opt.second,optr);
}
vector <int> trace;
void sol(){
cin>>n>>k;
for(int i=1; i<=n; i++) cin>>a[i],p[i]=p[i-1]+a[i];
for(int j=1; j<=k; j++){
for(int i=1; i<n; i++) dp[j&1][i]=0;
dnc(j,j,n-1,1,n);
}
ll ans=0;
for(int i=1; i<n; i++) ans=max(ans,dp[k&1][i]);
cout<<ans<<"\n";
int pos=0;
for(int i=1; i<n; i++) if(dp[k&1][i]==ans) pos=i;
for(int i=k; i; i--) trace.push_back(pos),pos=op[i][pos]-1;
reverse(trace.begin(),trace.end());
for(auto x:trace) cout<<x<<" ";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("sequence.in", "r", stdin);
// freopen("sequence.out", "w", stdout);
int tt=1;
//cin>>tt;
while(tt--){
sol();
}
cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
