#include <bits/stdc++.h>
using namespace std;
long long n,k;
long long s[100005];
long long dp[100005][205];
long long last[100005][205];
void solve(int nr, int st, int dr, int stOpt, int drOpt)
{
if(st > dr)
return;
int mij=(st+dr)/2;
long long maxi=-1, best=mij;
for(int j=stOpt; j<=min(mij, drOpt); j++)
{
long long nans = (s[mij]-s[j-1])*s[j-1] + dp[j-1][nr-1];
if(nans >= maxi)
{
maxi=nans;
best=j;
}
}
dp[mij][nr]=maxi;
last[mij][nr]=best-1;
solve(nr, st, mij-1, stOpt, best);
solve(nr, mij+1, dr, best, drOpt);
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i] += s[i-1];
}
for(int i=1;i<=k;i++)
solve(i, 1, n, 1, n);
cout<<dp[n][k]<<'\n';
int p=n;
int nr=k;
vector<int> ans;
while(true)
{
p=last[p][nr];
nr--;
if(p <= 0)
break;
ans.push_back(p);
}
reverse(ans.begin(), ans.end());
for(int it : ans)
cout<<it<<' ';
return 0;
}
