#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define MAXK 205
ll a[MAXN];
ll dp[MAXN][MAXK];
int opti[MAXN][MAXK];
const ll INF = 1e18;
void divide(int idx,int l,int r,int optl,int optr)
{
if(l>r)return ;
int opt = -1;
ll ans = -INF;
int i = (l+r)/2;
for(int j = optl; j <= optr; j++)
{
if(dp[idx-1][j]+a[j]*(a[i]-a[j])>ans)
{
ans=dp[idx-1][j]+a[j]*(a[i]-a[j]);
opt=j;
}
}
dp[idx][i]=ans;
opti[idx][i]=opt;
divide(idx,l,i-1,optl,opt);
divide(idx,i+1,r,opt,optr);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,k;
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i],a[i]+=a[i-1];
for(int i = 1; i <= k; i++)
{
divide(i,1,n,1,n);
}
cout << dp[k][n] << "\n";
int now = n;
while(k>0)
{
cout << opti[k][now] << " ";
now=opti[k][now];
k--;
}
return 0;
}
