#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cassert>
#define INF 1e18
long long Sum[100005];
long long SumSq[100005];
long long DP[100005][2];
int Last[100005][205];
typedef struct line line;
struct line
{
long long m, c;
double s;
int i;
};
line Lines[100005];
int L;
long long max(long long a, long long b)
{
return (a > b)?a:b;
}
int compare(long long x, line l)
{
return x < l.s;
}
int I, J;
long long getLine(long long x)
{
int i;
// for (i = 17; i >= 0; i--)
// {
// if (J + (1 << i) < L && Lines[J + (1 << i)].s <= x)
// J += (1 << i);
// }
while (J + 1 < L && Lines[J + 1].s <= x)
J++;
// int j = std::upper_bound(&Lines[0], &Lines[L], x, compare) - &Lines[0] - 1;
I = Lines[J].i;
return Lines[J].m*x + Lines[J].c;
}
double intersect(long long m, long long c, long long m2, long long c2)
{
if (m == m2)
{
if (c2 >= c)
return -INF;
else
return INF;
}
else
return (double) (c2 - c)/(m - m2);
}
void insertLine(int ii, long long m, long long c)
{
double s;
// int i;
// for (i = 17; i >= 0; i--)
// {
// if (L - (1 << i) >= 0 && (s = intersect(Lines[L - (1 << i)].m, Lines[L - (1 << i)].c, m, c)) <= Lines[L - (1 << i)].s)
// {
// L -= (1 << i);
// }
// }
while (L > 0 && (s = intersect(Lines[L - 1].m, Lines[L - 1].c, m, c)) <= Lines[L - 1].s)
L--;
if (s != INF)
{
Lines[L] = {m, c, s, ii};
L++;
}
}
int main()
{
int N, K;
scanf("%d %d", &N, &K);
int n, k, i;
for (i = 0; i < N; i++)
{
scanf("%lld", &Sum[i]);
if (i > 0)
Sum[i] += Sum[i - 1];
SumSq[i] = Sum[i]*Sum[i];
}
// Lines.push_back({0, 0, 0});
long long r;
for (k = 0; k <= K; k++)
{
L = 1;
J = 0;
Lines[0] = {0, 0, -INF, -1};
for (n = 0; n < N; n++)
{
DP[n][k%2] = getLine(Sum[n]);
Last[n][k] = I;
// for (i = 0; i < n; i++)
// {
// if (DP[i][k - 1] + Sum[i]*(Sum[n] - Sum[i]) > DP[n][k])
// {
// DP[n][k] = max(DP[n][k], DP[i][k - 1] + Sum[i]*(Sum[n] - Sum[i]));
// Last[n][k] = i;
// }
// }
if (k > 0 && n < N - 1)
insertLine(n, Sum[n], DP[n][(k - 1)%2] - SumSq[n]);
// printf("DP[%d][%d] = %lld\n", n, k, DP[n]);
}
// printf("k%d\n", k);
}
printf("%lld\n", DP[N - 1][K%2]);
i = Last[N - 1][K];
k = K - 1;
std::vector<int> V;
while (k >= 0 && i != -1)
{
V.push_back(i + 1);
i = Last[i][k];
k--;
}
for (i = V.size() - 1; i >= 0; i--)
printf("%d ", V[i]);
}
