#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, K = 205;
const ll inf = 1e18;
ll dp[K][N], pref[N], path[K][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++)
{
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);
compute(k, mid + 1, 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;
}
for(int i = 1; i <= k; i++)
for(int j = 0; j <= n; j++)
dp[i][j] = -inf;
for(int i = 1; i <= k; i++)
compute(i, 0, n+1, 0, n+1);
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;
}
