// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
#define fi first
#define se second
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l,int r){return l+((hdp()%(r-l+1))+r-l+1)%(r-l+1);}
const int N = 1e5+5;
const int mod = 1e9+7;
const int SQ = 450;
const int inf = 1e16;
unsigned int n,m,a[N],dp[2][N],cur,p[N];
int32_t par[205][N];
int cost(int l,int r)
{
return (p[r]-p[l-1])*p[l-1];
}
void dnc(int l,int r,int optl,int optr)
{
if(l>r) return;
int m=l+r>>1;
pair<int,int> best={-inf,-1};
for(int k=optl;k<=min(m,optr);k++) best=max(best,{dp[cur&1^1][k-1]+cost(k,m),k});
dp[cur&1][m]=best.fi;
int opt=best.se;
par[cur][m]=opt-1;
dnc(l,m-1,optl,opt);
dnc(m+1,r,opt,optr);
}
signed main()
{
fastIO
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
p[i]=p[i-1]+a[i];
}
for(int i=1;i<=m;i++)
{
cur=i;
dnc(1,n,1,n);
}
cout<<dp[m&1][n]<<endl;
int x=m,y=n;
while(x)
{
cout<<par[x][y]<<' ';
y=par[x][y];
x--;
}
}
