#include <bits/stdc++.h>
using namespace std;
const long long inf = -1e18;
const long long mod = 1e9 + 7;
const int MaxN = 1e5 + 5;
const int MaxK = 2e2 + 5;
int n, k;
long long arr[MaxN];
void Inp()
{
cin >> n >> k;
k++;
for (int x = 1; x <= n; x++)
{
cin >> arr[x];
}
}
struct Line
{
long long a, b;
int id;
Line() = default;
Line(long long _a, long long _b, int _id)
{
a = _a;
b = _b;
id = _id;
}
};
vector<Line> hull;
vector<long double> intersect;
int curptr;
bool Check(const Line& a, const Line& b, const Line& c)
{
return (long double)(c.b - a.b) / (long double)(a.a - c.a) > (long double)(b.b - a.b) / (long double)(a.a - b.a);
}
void Reset()
{
hull.clear();
intersect.clear();
curptr = 0;
}
void Add(const Line& k)
{
if (!hull.empty() && hull.back().a == k.a)
{
if (hull.back().b < k.b)
{
hull.pop_back();
intersect.pop_back();
while ((int)hull.size() >= 2)
{
Line p = hull.back();
hull.pop_back();
if (Check(hull.back(), p, k))
{
hull.push_back(p);
break;
}
intersect.pop_back();
}
curptr = min(curptr, (int)hull.size() - 1);
if (!hull.empty())
{
intersect.pop_back();
intersect.push_back((long double)((long double)(k.b - hull.back().b) / (long double)(hull.back().a - k.a)));
}
hull.push_back(k);
intersect.push_back(-inf);
}
return;
}
while ((int)hull.size() >= 2)
{
Line p = hull.back();
hull.pop_back();
if (Check(hull.back(), p, k))
{
hull.push_back(p);
break;
}
intersect.pop_back();
}
curptr = min(curptr, (int)intersect.size() - 1);
if (!hull.empty())
{
intersect.pop_back();
curptr = min(curptr, (int)intersect.size() - 1);
intersect.push_back((long double)((long double)(k.b - hull.back().b) / (long double)(hull.back().a - k.a)));
}
hull.push_back(k);
intersect.push_back(-inf);
}
pair<long long, int> Query(long long x)
{
assert(!hull.empty());
curptr = max(curptr, 0);
while (curptr < (int)intersect.size() && intersect[curptr] <= (long double)x)
{
curptr++;
}
return make_pair(hull[curptr].a * x + hull[curptr].b, hull[curptr].id);
}
long long sum[MaxN];
int track[202][MaxN];
pair<long long, int> F[2][MaxN];
void Exc()
{
for (int x = 1; x <= n; x++)
{
sum[x] = sum[x - 1] + arr[x];
}
F[0][0] = make_pair(0, 0);
for (int x = 1; x <= n; x++)
{
F[0][x] = make_pair(inf, 0);
}
for (int x = 1; x <= k; x++)
{
Reset();
for (int y = 0; y < x; y++)
{
F[x & 1][y] = make_pair(inf, 0);
}
Add(Line(sum[x - 1], F[(x & 1) ^ 1][x - 1].first - sum[x - 1] * sum[x - 1], x - 1));
for (int y = x; y <= n; y++)
{
F[x & 1][y] = Query(sum[y]);
Add(Line(sum[y], F[(x & 1) ^ 1][y].first - sum[y] * sum[y], y));
}
for (int y = 0; y <= n; y++)
{
track[x][y] = F[x & 1][y].second;
}
}
pair<long long, int> res = F[k & 1][n];
cout << res.first << "\n";
int cur = k;
while (res.second > 0)
{
cout << res.second << " ";
cur--;
res.second = track[cur][res.second];
}
}
int main()
{
//freopen("B.INP", "r", stdin);
//freopen("B.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
//cin >> test;
for (int w = 1; w <= test; w++)
{
Inp();
Exc();
}
return 0;
}
