#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
ll cnt,sz,n,k,p[100006],dp[100002][5];
int sv[100002][202],st[100005],v[100006];
vector<int> anw;
double get(ll a,ll b,ll q)
{
a=st[a],b=st[b];
if(p[a]==p[b]) return -1e15;
return (double)(p[b]*p[b]-p[a]*p[a]+dp[a][q%2]-dp[b][q%2])/(double)(p[b]-p[a]);
}
void push(ll x,ll d)
{
st[sz]=x;
while(sz>=2&&get(sz,sz-1,d)<get(sz-1,sz-2,d))
{
sz--,st[sz]=x;
}
sz++;
}
ll val(ll x,ll d)
{
while(cnt<sz-1&&p[x]>=get(cnt,cnt+1,d)) cnt++;
ll nw=st[cnt];
sv[x][d+1]=nw;
return p[x]*p[nw]-p[nw]*p[nw]+dp[nw][d%2];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>v[i],p[i]=p[i-1]+(ll)v[i];
for(int i=1;i<=k;i++)
{
cnt=0,sz=0;
push(0,0);
for(int j=1;j<=n;j++)
{
dp[j][i%2]=val(j,i-1);
push(j,i-1);
}
}
cout<<dp[n][k%2]<<"\n";
ll g=n;
for(int i=k;i>=1;i--)
{
g=sv[g][i];
anw.push_back(g);
}
reverse(anw.begin(),anw.end());
for(int i=0;i<k;i++)
cout<<anw[i]<<" ";
return 0;
}
