#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define MOD 998244353
const int N = 100005, lg = 205;
int q[N], p[lg][N];
ll a[N], tmp1[N], tmp2[N];
void path(int k, int n)
{
if (k < 0)
return;
path(k - 1, p[k][n]);
cout << n << ' ';
}
void solve()
{
int n, k, f, r;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] += a[i - 1];
tmp1[i] = -a[i] * a[i];
}
for (int i = 1; i <= k; i++)
{
f = 1;
r = 1;
q[1] = i;
for (int j = i + 1; j <= n; j++)
{
while (f < r and a[q[f]] * a[j] + tmp1[q[f]] <= a[q[f + 1]] * a[j] + tmp1[q[f + 1]])
{
f++;
}
tmp2[j] = a[q[f]] * a[j] + tmp1[q[f]] - a[j] * a[j], p[i][j] = q[f];
while (f < r and (tmp1[q[r]] - tmp1[q[r - 1]]) * (a[q[r - 1]] - a[j]) >= (tmp1[j] - tmp1[q[r - 1]]) * (a[q[r - 1]] - a[q[r]]))
{
r--;
}
r++;
q[r] = j;
}
for (int j = i + 1; j <= n; j++)
{
tmp1[j] = tmp2[j];
}
}
cout << tmp1[n] + a[n] * a[n] << '\n';
path(k - 1, p[k][n]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
// cout << fixed << setprecision(12);
for (int i = 1; i <= t; i++)
{
solve();
}
}
