/*input
7 3
4 1 3 4 0 2 3
*/
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
//using ull = __ull128_t;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
ll mod = 1e9 + 7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll power(ll a, ll b)
{
if (abs(a) >= mod)
a %= mod;
if (abs(b) >= mod - 1)
b %= (mod - 1);
if (a < 0)
a += mod;
if (b < 0)
b += mod - 1;
ll r = 1;
if (b % 2 == 1)
r = a;
b /= 2;
while (b)
{
a = (a * a) % mod;
if (b % 2 == 1)
r = (r * a) % mod;
b /= 2;
}
return r;
}
vector<pair<ll, ll>>V;
vector<int>Vi;
int itv = 0;
void reset()
{
V.clear();
Vi.clear();
itv = 0;
}
ld C(pair<ll, ll>a, pair<ll, ll>b)
{
ld k = a.first - b.first;
ld c = a.second - b.second;
//kx+c=0;
return -c / k;
}
void add(ll c, ll k, int i)
{
if (V.size() > 0 && V.back().first == k && V.back().second >= c)
return;
if (V.size() > 0 && V.back().first == k)
{
V.back().second = c;
Vi.back() = i;
}
else {
V.push_back({k, c});
Vi.push_back(i);
}
while (V.size() >= 3)
{
pair<ll, ll>a = V[V.size() - 3];
pair<ll, ll>b = V[V.size() - 2];
pair<ll, ll>c = V[V.size() - 1];
if (C(a, b) > C(b, c) + 1e-9)
{
V.erase(V.begin() + (V.size() - 2));
Vi.erase(Vi.begin() + (Vi.size() - 2));
}
else
break;
}
}
pair<ll, int> get(ll x)
{
itv = min(itv, (int)V.size() - 1);
ll v = V[itv].first * x + V[itv].second;
while (itv + 1 < (int)V.size())
{
ll v1 = V[itv + 1].first * x + V[itv + 1].second;
if (v1 >= v)
{
v = v1;
itv++;
}
else
break;
}
while (itv > 0)
{
ll v1 = V[itv - 1].first * x + V[itv - 1].second;
if (v1 >= v)
{
v = v1;
itv--;
}
else
break;
}
return {v, Vi[itv]};
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, K;
cin >> n >> K;
K++;
ll a[n + 1];
a[0] = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] += a[i - 1];
}
ll dp[n + 1][2];
int dp1[n + 1][K + 1];
for (int r = 1; r <= n; r++)
dp[r][1] = 0;
for (int k = 2; k <= K; k++)
{
int k1 = (k - 1) % 2;
int k2 = k % 2;
reset();
for (int r = k; r <= n; r++)
{
add(dp[r - 1][k1] - a[r - 1] * a[r - 1], a[r - 1], r - 1);
//for (int r1 = k - 1; r1 <= r - 1; r1++)
{
//ll gal = dp1[r1][k - 1].first - a[r1] * a[r1] + a[r] * a[r1];
pair<ll, int>v = get(a[r]);
dp[r][k2] = v.first;
dp1[r][k] = v.second;
}
}
}
int k = K;
cout << dp[n][k % 2] << "\n";
vector<int>ans;
while (k > 1)
{
n = dp1[n][k];
ans.push_back(n);
k--;
assert(n >= 1 && k <= n);
}
sort(ans.begin(), ans.end());
for (ll n : ans)
cout << n << " ";
cout << "\n";
}
