#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
ll intersection(ll k, ll b, ll k1, ll b1)
{
if (k == k1)
return -1;
return (ll)((b1 - b) / (k - k1 + 0.0));
}
void solve()
{
ll n, k;
cin >> n >> k;
ll dp[2][n + 1], a[n + 1];
int best[k + 1][n + 1];
for (ll i = 0; i <= k; i++)
for (ll j = 0; j <= n; j++)
best[i][j] = 0;
a[0] = 0;
for (ll i = 1; i <= n; i++)
cin >> a[i], a[i] += a[i - 1];
for (ll i = 0; i <= n; i++)
dp[0][i] = 0, dp[1][i] = -1e18;
vector<array<ll, 3>> v;
array<ll, 3> cur;
for (ll i = 1; i <= k; i++)
{
v.clear();
for (ll j = 0; j <= n; j++)
{
cur = {0, (ll)1e18, j};
// while (!v.empty() and v.back()[0] * a[v.back()[2]] + dp[(i + 1) & 1][v.back()[2]] - a[v.back()[2]] * a[n] < v.back()[0] * a[j] + dp[(i + 1) & 1][j] - a[j] * a[n])
// v.pop_back();
if (v.empty())
v.push_back({0, (ll)1e18, j});
// else
// {
// ll point = intersection(a[v.back()[2]], dp[(i + 1) & 1][v.back()[2]], a[j], dp[(i + 1) & 1][j]);
// if (point != -1)
// v.back()[1] = point, cur[0] = point + 1, v.push_back(cur);
// }
}
for (ll j = 1, pos; j <= n; j++)
{
pos = upper_bound(v.begin(), v.end(), array<ll, 3>{a[j], (ll)1e18, (ll)1e18}) - v.begin();
for (ll m = max(0ll, pos - 100); m <= min((ll)v.size() - 1, pos + 100); m++)
if (dp[i & 1][j] < dp[(i + 1) & 1][v[m][2]] + (a[j] - a[v[m][2]]) * (a[n] - a[j]))
dp[i & 1][j] = dp[(i + 1) & 1][v[m][2]] + (a[j] - a[v[m][2]]) * (a[n] - a[j]), best[i][j] = v[m][2];
}
}
pair<ll, ll> ans = make_pair(-1, 0);
for (ll i = 1; i < n; i++)
ans = max(ans, make_pair(dp[k & 1][i], i));
cout << ans.first << endl;
ll x = ans.second;
for (ll i = k; i >= 1; i--)
cout << x << " ", x = best[i][x];
cout << endl;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t = 1;
// precomp();
// cin >> t;
for (ll i = 1; i <= t; i++)
solve();
cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}
