#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
int n,k;
int bef[205][100005];
ll a[100005],pre[100005],dp[2][100005],q[100005],l=1,r=1;
bool case1(int x, int y, int i) {
return (dp[0][y] - dp[0][x] >= (pre[y] - pre[x]) * (pre[n] - pre[i]));
}
bool case2(int x, int y, int i) {
return ((dp[0][y] - dp[0][x]) * (pre[i] - pre[y]) <=
(dp[0][i] - dp[0][y]) * (pre[y] - pre[x]));
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>k;
pre[0]=0;
for(ll i=1;i<=n;i++){
cin>>a[i];
pre[i]=pre[i-1]+a[i];
}
fill(dp[0],dp[0]+n+5,0);
for(ll j=1;j<=k;j++){
q[r]=0;
r++;
for(ll i=1;i<=n;i++){
while(r-l>1&&case1(q[l],q[l+1],i)){
l++;
}
ll x=q[l];
dp[1][i]=dp[0][x]+(pre[i]-pre[x])*(pre[n]-pre[i]);
bef[j][i]=x;
while(r-l>1&&case2(q[r-2],q[r-1],i)){
r--;
}
q[r++]=i;
}
l=1;
r=1;
for(ll i=1;i<=n;i++){
dp[0][i]=dp[1][i];
}
}
ll mx=-1,ind=-1;
for(ll i=1;i<=n;i++){
if(dp[0][i]>mx){
mx=dp[0][i];
ind=i;
}
}
cout<<mx<<"\n";
for(ll i=0;i<k;i++){
cout<<ind<<' ';
ind=bef[k-i][ind];
}
}
