#include <iostream>
#include <deque>
using namespace std;
/*
dp[c][i] = min{dp[c-1][j] + (a_sum[i] - a_sum[j]) * a_sum[j] | 1 <= j < i}
= min{a_sum[j] * a_sum[i] + dp[c-1][j] - a_sum[j]^2 | 1 <= j < i}
A * X + B
*/
struct line
{
long long a;
long long b;
int i;
long long eval(long long x)
{
return a*x + b;
}
};
long long sq(long long x)
{
return x*x;
}
bool intersect_comp(line l1, line l2, line r1, line r2)
{
//intersect(l1, l2) <=> l1.a * x + l1.b == l2.a * x + l2.b
/*
xL = (l2.b - l1.b)/(l1.a - l2.a)
xR = (r2.b - r1.b)/(r1.a - r2.a)
xL < xR <=> ()
*/
return (l2.b - l1.b)*(r1.a - r2.a) < (r2.b - r1.b)*(l1.a - l2.a);
}
int main()
{
int n, k;
cin >> n >> k;
long long a[n+1], a_sum[n+1];
a_sum[0] = 0;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
a_sum[i] = a[i] + a_sum[i-1];
}
long long* dp[k+1];
int* prev[k+1];
dp[0] = new long long[n+1];
dp[1] = new long long[n+1];
prev[0] = new int[n+1];
prev[1] = new int[n+1];
for(int x = 2; x <= k; x++)
{
dp[x] = dp[x-2];
prev[x] = new int[n+1];
}
for(int i = 0; i <= n; i++)
{
dp[0][i] = 0;
prev[0][i] = 0;
}
for(int c = 1; c <= k; c++)
{
prev[c][1] = 0;
dp[c][1] = 0;
deque<line> cht;
cht.push_back(line{a_sum[1], dp[c-1][1] - sq(a_sum[1]), 1});
for(int i = 2; i <= n; i++)
{
while(cht.size() > 1 && cht[0].eval(a_sum[i]) <= cht[1].eval(a_sum[i]))
cht.pop_front();
dp[c][i] = cht[0].eval(a_sum[i]);
prev[c][i] = cht[0].i;
line new_line = line{a_sum[i], dp[c-1][i] - sq(a_sum[i]), i};
while(cht.size() > 1 && !intersect_comp(cht[cht.size()-2], cht[cht.size()-1], cht.back(), new_line))
cht.pop_back();
cht.push_back(new_line);
}
}
cout << dp[k][n] << '\n';
int x = n, y = k;
for(y = k; y >= 1; y--)
{
cout << prev[y][x] << ' ';
x = prev[y][x];
}
cout << '\n';
}
