#include <bits/stdc++.h>
// author: aykhn
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define mpr make_pair
#define eb emplace_back
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define ins insert
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount
const int MXN = 1e5 + 5, MXK = 2e2 + 5;
int n, k;
ll a[MXN], pref[MXN];
int par[MXN][MXK];
ll l[MXN], r[MXN];
ll intersection(ll k1, ll b1, ll k2, ll b2)
{
int neg = ((b2 - b1 < 0) ^ (k1 - k2 < 0));
ll a = abs(b2 - b1);
ll b = abs(k1 - k2);
ll i = a / b;
if (neg) i = -i;
else if (a % b) i = i + 1;
return i;
}
ll comp(ll k1, ll b1, ll k2, ll b2, int ind)
{
if (k1 == k2) return b2 >= b1;
ll i = intersection(k1, b1, k2, b2);
return i <= l[ind];
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
cin >> n >> k;
k++;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
vector<ll> dp(n + 1, 0);
for (int i = 1; i <= n; i++) dp[i] = pref[i] * (pref[n] - pref[i]);
for (int j = 2; j <= k; j++)
{
vector<ll> ndp(n + 1, 0);
vector<int> st;
for (int i = 1; i <= n; i++)
{
if (i > 1)
{
ll x = pref[i] - pref[n];
int lx = 0;
int rx = (int)st.size() - 1;
while (lx < rx)
{
int mid = (lx + rx + 1) >> 1;
if (l[mid + 1] <= x) lx = mid;
else rx = mid - 1;
}
int k1 = st[lx];
ndp[i] = pref[k1] * (pref[i] - pref[n]) + dp[k1] + pref[i] * pref[n] - pref[i] * pref[i];
par[i][j] = k1;
}
while (!st.empty() && comp(pref[st.back()], dp[st.back()], pref[i], dp[i], st.size()))
{
st.pop_back();
}
if (st.empty())
{
l[1] = -infll;
r[1] = infll;
}
else
{
r[st.size()] = intersection(pref[st.back()], dp[st.back()], pref[i], dp[i]) - 1;
l[st.size() + 1] = r[st.size()] + 1;
r[st.size() + 1] = infll;
}
st.push_back(i);
}
swap(dp, ndp);
}
cout << dp[n] << '\n';
int x = n;
int y = k;
vector<int> v;
while (y > 1)
{
x = par[x][y];
y--;
v.pb(x);
}
sort(all(v));
for (int x : v) cout << x << ' ';
cout << '\n';
}
