#include <bits/stdc++.h>
using namespace std;
#define MAX 100100
#define MAXK 202
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define __buitin_popcount __builtin_popcountll
#define BIT(x,i) (((x)>>(i))&1ll)
#define MASK(i) (1ll<<(i))
template<class X,class Y> bool maximize(X &x,Y y)
{
if(x<y)
{
x=y;
return 1;
}
return 0;
}
template<class X,class Y> bool minimize(X &x,Y y)
{
if(y<x)
{
x=y;
return 1;
}
return 0;
}
const int inf=1e9+412009;
const ll INF=2e18+412009;
int n,K;
int a[MAX];
void nhap()
{
cin>>n>>K;
for(int i=1;i<=n;i++) cin>>a[i];
}
ll dp[MAX][2]={};
int trace[MAX][MAXK]={};
ll f[MAX];
double get(int i,int j)
{
if(f[j]-f[i]==0) return 0;
return 1.0*(dp[j][0]-dp[i][0])/(f[j]-f[i]);
}
void solve()
{
for(int i=1;i<=n;i++) f[i]=f[i-1]+a[i];
for(int i=1;i<=n;i++) dp[i][1]=f[i]*(f[n]-f[i]);
for(int k=2;k<=K;k++)
{
for(int i=1;i<=n;i++) dp[i][0]=dp[i][1],dp[i][1]=0;
deque<int> dq;
dq.push_back(k-1);
for(int i=k;i<=n;i++)
{
while(dq.size()>1&&get(dq[0],dq[1])>=f[n]-f[i]) dq.pop_front();
int j=dq.front();
dp[i][1]=dp[j][0]+(f[i]-f[j])*(f[n]-f[i]);
trace[i][k]=j;
while(dq.size()>1&&get(dq.back(),i)>=get(dq[(int)dq.size()-2],i)) dq.pop_back();
dq.push_back(i);
}
}
ll ans=dp[K][1];
int u=K;
for(int i=1;i<=n;i++)
{
if(maximize(ans,dp[i][1])) u=i;
}
cout<<ans<<'\n';
stack<int> tracing;
int v=K;
while(v!=0)
{
tracing.push(u);
u=trace[u][v];
v--;
}
while(!tracing.empty()) cout<<tracing.top()<<' ',tracing.pop();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
// freopen("SPLIT_THE_SEQUENCE_APIO14.INP","r",stdin);
// freopen("SPLIT_THE_SEQUENCE_APIO14.OUT","w",stdout);
nhap();
solve();
return 0;
}
