#include <bits/stdc++.h>
#define int long long
using namespace std;
const int oo = INT_MAX;
int n,k;
int v[100005];
int sp[100005];
int dp[100005][2];
signed l[100005][205];
int sum(int st, int dr)
{
if(st > dr)
{
return 0;
}
return sp[dr] - sp[st - 1];
}
void divide(int st, int dr, int min_chosen, int max_chosen, int j)
{
if(st > dr)
{
return;
}
int mij = (st + dr) >> 1;
dp[mij][j % 2] = -oo;
for(int p=min_chosen; p<=min(max_chosen,mij); p++)
{
if(dp[p-1][(j-1) % 2] + sum(p,mij) * sum(mij + 1, n) >= dp[mij][j % 2])
{
dp[mij][j % 2] = dp[p-1][(j-1) % 2] + sum(p,mij) * sum(mij + 1, n);
l[mij][j] = p - 1;
}
}
divide(st,mij-1,min_chosen,l[mij][j] + 1,j);
divide(mij+1,dr,l[mij][j]+1,max_chosen,j);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
++k;
for(int i=1; i<=n; i++)
{
cin>>v[i];
sp[i] = sp[i-1] + v[i];
}
for(int i=1; i<=n; i++)
{
dp[i][1] = sum(1,i) * sum(i + 1, n);
}
for(int j=2; j<=k; j++)
{
divide(1,n,1,n,j);
}
cout<<dp[n][k % 2]<<'\n';
int poz = n;
vector<int> rez;
while(poz)
{
poz = l[poz][k--];
if(poz)
{
rez.push_back(poz);
}
}
reverse(rez.begin(),rez.end());
for(auto it : rez)
{
cout<<it<<' ';
}
cout<<'\n';
return 0;
}
