#include<bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define task "name"
const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int N = 1e5 + 3;
const int BASE = 10;
const int LOG = 20;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
int n, k;
int pre[N];
int f[203][N];
int pos[203][N];
int trace[203][N];
void dnc(int g, int l, int r, int from, int to)
{
if(l > r) return;
int mid = (l + r)/2;
for(int i = from; i <= min(to, mid); i++)
{
if(f[g][mid] < f[g - 1][i - 1] + (pre[mid] - pre[i - 1]) * (pre[n] - pre[mid]))
{
f[g][mid] = f[g - 1][i - 1] + (pre[mid] - pre[i - 1]) * (pre[n] - pre[mid]);
pos[g][mid] = i;
}
}
trace[g][mid] = pos[g][mid] - 1;
dnc(g, l, mid - 1, from, pos[g][mid]);
dnc(g, mid + 1, r, pos[g][mid], to);
}
void Solve()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
int a;
cin >> a;
pre[i] = pre[i - 1] + a;
}
memset(f, -0x3f, sizeof f);
for(int i = 1; i <= n; i++) f[1][i] = pre[i] * (pre[n] - pre[i]);
for(int i = 2; i <= k + 1; i++)
dnc(i, 1, n, 1, n);
cout << f[k + 1][n] << '\n';
vector<int> ans;
int t = trace[k + 1][n];
ans.pb(t);
for(int i = k; i >= k - 1; i--)
{
t = trace[i][t];
ans.pb(t);
}
reverse(all(ans));
for(int i : ans) cout << i << " ";
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int T = 1;
//cin >> T;
while(T--)
{
Solve();
}
return 0;
}
