#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 1;
const int INF = LLONG_MAX;
int n, k;
int a[MAXN];
int pre[MAXN], suf[MAXN];
int dp[201][MAXN];
vector<int> trace;
struct Line
{
int a, b;
mutable int p;
bool operator<(const Line& o) const
{
if (o.a == LLONG_MAX && o.b == LLONG_MAX) return p < o.p;
return a < o.a;
}
};
struct LineContainer
{
multiset<Line> s;
int divi(int a, int b)
{
if (b == 0) return (a > 0 ? INF : -INF);
int q = a / b;
if ((a ^ b) < 0 && a % b) --q;
return q;
}
bool isect(multiset<Line>::iterator x, multiset<Line>::iterator y)
{
if (y == s.end())
{
x->p = INF;
return false;
}
if (x->a == y->a)
x->p = (x->b > y->b) ? INF : -INF;
else
x->p = divi(y->b - x->b, x->a - y->a);
return x->p >= y->p;
}
void add(int a_, int b_)
{
auto it = s.insert({a_, b_, 0});
auto y = next(it);
while (isect(it, y)) y = s.erase(y);
if (it != s.begin())
{
auto x = it;
--x;
if (isect(x, it))
isect(x, s.erase(it));
}
while (true)
{
auto y = it;
if (y == s.begin()) break;
--y;
if (y->p < it->p) break;
isect(y, s.erase(it));
it = y;
}
}
int query(int x)
{
Line q{LLONG_MAX, LLONG_MAX, x};
auto it = s.lower_bound(q);
if (it == s.end()) --it;
return it->a * x + it->b;
}
bool empty()
{
return s.empty();
}
};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
for (int i = 1; i <= n; ++i)
{
pre[i] = pre[i - 1] + a[i];
}
for (int i = n; i >= 1; --i)
{
suf[i] = suf[i + 1] + a[i];
}
for (int t = 0; t <= k; ++t)
{
for (int i = 0; i <= n; ++i)
{
dp[t][i] = LLONG_MIN;
}
}
for (int i = 1; i <= n-1; ++i)
{
dp[1][i] = pre[i] * suf[i + 1];
}
if (k == 1)
{
int ans = LLONG_MIN;
int point = 0;
for (int i = 1; i <= n-1; ++i)
{
if (ans < dp[1][i])
{
ans = dp[1][i];
point = i;
}
}
cout << ans << "\n";
cout << point;
return 0;
}
for (int t = 2; t <= k; ++t)
{
LineContainer cht;
for (int i = t - 1; i <= n - 1; ++i)
{
if (dp[t-1][i] != LLONG_MIN)
{
cht.add(-pre[i], dp[t-1][i]);
}
int nxt = i + 1;
if (nxt >= t && nxt <= n - 1 && !cht.empty())
{
int cur = cht.query(suf[nxt + 1]);
if (cur != LLONG_MIN)
{
dp[t][nxt] = cur + suf[nxt + 1] * pre[nxt];
}
}
}
}
int ans = LLONG_MIN;
int point = 0;
for (int i = k; i <= n - 1; ++i)
{
if (ans < dp[k][i])
{
ans = dp[k][i];
point = i;
}
}
trace.push_back(point);
for (int j = k - 1; j >= 1; j--)
{
for (int i = 1; i < point; i++)
{
if (dp[j + 1][point] == dp[j][i] + (pre[point] - pre[i]) * suf[point + 1])
{
point = i;
trace.push_back(point);
break;
}
}
}
reverse(trace.begin(), trace.end());
cout << ans << "\n";
for (auto v : trace)
{
cout << v << " ";
}
}
