/** Im the best because i work as hard as i possibly can **/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl "\n"
const int N = 15e4 + 10;
const ll inf = 1e18;
int n, k, par[210][N];
ll dp[2][N], ps[N], A[N];
inline ll calc(int l, int m)
{
return (ps[n] - ps[m]) * (ps[m] - (l <= 0? 0 : ps[l - 1]));
}
void solve(int j, int l, int r, int le, int ri)
{
int j2 = j & 1;
if(l > r || le > ri) return;
int mid = (l + r) >> 1, opt = le;
dp[j2][mid] = -inf;
ll best = -inf;
for(int i = max(1, le); i <= min(mid, ri); i ++)
{
ll cu = dp[1 ^ j2][i - 1] + calc(i, mid);
if(cu > best)
{
best = cu;
opt = i;
}
}
dp[j2][mid] = best;
par[j][mid] = opt - 1;
solve(j, l, mid - 1, le, opt);
solve(j, mid + 1, r, max(le, opt), ri);
}
int main()
{
scanf("%d%d", &n, &k);
k ++;
for(int i = 1; i <= n; i ++)
{
scanf("%lld", &A[i]);
ps[i] = ps[i - 1] + A[i];
}
for(int i = 1; i < N; i ++) dp[0][i] = -inf;
for(int j = 1; j <= k; j ++)
{
solve(j, 1, n, 1, n);
}
printf("%lld\n", dp[k & 1][n]);
vector < int > ans;
int i = n, j = k;
while(j > 0 && i > 0 && par[j][i] > 0)
{
ans.push_back(par[j][i]);
i = par[j][i];
j --;
}
reverse(all(ans));
for(auto x : ans) printf("%d ", x);
return 0;
}
