#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, K = 205;
const ll inf = 1e18;
vector<vector<ll> > dp;
vector<vector<int> > path;
vector<ll> pref(N);
void compute(int &k, int &l, int &r, int &s, int &e)
{
if(r <= l) return;
int mid = (l + r) / 2;
int bestj = s;
for(int i = s; i <= min(e, mid - 1); i++)
{
if(dp[k - 1][i] == -inf) continue;
ll val = dp[k - 1][i] + (pref[mid] - pref[i]) * pref[i];
if(val > dp[k][mid])
dp[k][mid] = val, bestj = i;
}
path[k][mid] = bestj;
compute(k, l, mid, s, bestj);
mid++;
compute(k, mid, r, bestj, e);
}
int main()
{
int n, k;
cin >> n >> k;
pref[0] = 0;
for(int i = 1; i <= n; i ++)
{
int x; cin >> x;
pref[i] = pref[i - 1] + x;
}
dp = vector<vector<ll> > (k + 1, vector<ll> (n + 1));
path = vector<vector<int> > (k + 1, vector<int> (n+1));
dp[0][0] = -inf;
for(int i = 1; i <= k; i++)
for(int j = 0; j <= n; j++)
dp[i][j] = -inf;
n++;
for(int i = 1; i <= k; i++) {
int z = 0;
compute(i, z, n, z, n);
/*
for(int j = 0; j <= n; j++)
for(int l = 0; l < j; l++)
if(dp[i - 1][l] != -inf)
{
ll val = dp[i - 1][l] + pref[l] * (pref[j] - pref[l]);
if(val >= dp[i][j])
dp[i][j] = val, path[i][j] = l;
}
*/
}
cout << dp[k][n] << endl;
int cur = n;
vector<int> ans = {};
int j = k;
while(j--)
{
cur = path[j + 1][cur];
ans.push_back(cur);
}
reverse(ans.begin(), ans.end());
for(int i : ans)
cout << i << ' ';
cout << endl;
return 0;
}
