#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 + 2;
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;
ll pre[N];
ll f[2][N];
int trace[202][N];
void dnc(int g, int l, int r, int from, int to)
{
if(l > r) return;
int mid = (l + r)/2;
pair<long long, int> best(-oo, 0);
int last = (1 ^ (g & 1));
int cur = last ^ 1;
for(int i = from; i <= min(to, mid); i++)
{
maximize(best, mp(f[last][i - 1] + (pre[mid] - pre[i - 1]) * (pre[n] - pre[mid]), i));
}
f[cur][mid] = best.fi;
trace[g][mid] = best.se - 1;
dnc(g, l, mid - 1, from, best.se);
dnc(g, mid + 1, r, best.se, to);
}
void Solve()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
ll a;
cin >> a;
pre[i] = pre[i - 1] + a;
}
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, i, n, 1, n);
cout << f[(k & 1) ^ 1][n] << '\n';
vector<int> ans;
int t = trace[k + 1][n];
ans.pb(t);
for(int i = k; i >= 2; i--)
{
t = trace[i][t];
if (t == 0) {
break;
}
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;
}
