#include <iostream>
#include <vector>
#define inf 1'000'000'000'000'000'000
#define int long long
#define EPS 0.00001
using namespace std;
struct ln
{
int m;
int c;
double p;
};
int a[100005];
int vs[100005];
int par[205][100005];
vector<int> dp(100005);
vector<int> ndp(100005);
vector<pair<ln, int>> cht;
double getx(int m, int c, int m1, int c1)
{
return (double)(c-c1)/(m1-m);
}
int gety(int x)
{
int rez = 0;
int l = 0, d = cht.size()-1;
while (l <= d)
{
int mid = (l+d)/2;
if (cht[mid].first.p <= x+EPS)
rez = mid, l = mid+1;
else
d = mid-1;
}
return cht[rez].second;
}
void vstavi(int m, int c, int ix)
{
double p = -inf;
while (!cht.empty())
{
p = getx(m, c, cht.back().first.m, cht.back().first.c);
if (p < cht.back().first.p)
cht.pop_back();
else
break;
}
cht.push_back({{m, c, p}, ix});
}
int32_t main()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
vs[i] = vs[i-1]+a[i];
}
for (int tk = 0; tk < k; tk++)
{
cht.clear();
cht.push_back({{0, 0}, 0});
for (int i = 1; i <= n; i++)
{
int p = gety(-vs[n]+vs[i]);
ndp[i] = dp[p] + (vs[i]-vs[p])*(vs[n]-vs[i]);
par[tk][i] = p;
vstavi(vs[i], dp[i], i);
}
dp = ndp;
}
int tr = n, mx = dp[n];
for (int i = 1; i <= n; i++)
{
if (dp[i] > mx)
{
mx = dp[i];
tr = i;
}
}
cout << mx << "\n";
for (int i = k-1; i >= 0; i--)
{
cout << tr << " ";
tr = par[i][tr];
}
cout << "\n";
return 0;
}
