#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
const long long NEG_INF = LLONG_MIN;
int n, k;
long long a[MAXN];
long long pre[MAXN], suf[MAXN];
long long dp_prev[MAXN], dp_cur[MAXN];
int par[205][MAXN];
vector<int> trace;
struct Line
{
long long m, b;
int id;
};
struct CHT
{
deque<Line> dq;
bool bad(const Line &l1, const Line &l2, const Line &l3)
{
__int128 left = (__int128)(l3.b - l1.b) * (l1.m - l2.m);
__int128 right = (__int128)(l2.b - l1.b) * (l1.m - l3.m);
return left >= right;
}
void add(long long m, long long b, int id)
{
Line ln = {m, b, id};
while (dq.size() >= 2 &&
bad(dq[dq.size()-2], dq.back(), ln))
dq.pop_back();
dq.push_back(ln);
}
pair<long long,int> query(long long x)
{
while (dq.size() >= 2 &&
dq[0].m * x + dq[0].b <= dq[1].m * x + dq[1].b)
dq.pop_front();
return {dq[0].m * x + dq[0].b, dq[0].id};
}
bool empty()
{
return dq.empty();
}
};
int 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 i = 0; i <= n; ++i)
dp_prev[i] = NEG_INF;
for (int i = 1; i <= n - 1; ++i)
dp_prev[i] = pre[i] * suf[i + 1];
if (k == 1)
{
long long ans = NEG_INF;
int pos = 0;
for (int i = 1; i <= n - 1; ++i)
{
if (dp_prev[i] > ans)
{
ans = dp_prev[i];
pos = i;
}
}
cout << ans << "\n";
cout << pos << "\n";
return 0;
}
for (int t = 2; t <= k; ++t)
{
CHT cht;
for (int i = 0; i <= n; ++i)
dp_cur[i] = NEG_INF;
for (int i = 1; i <= n - 1; ++i)
{
if (i - 1 >= t - 1 && dp_prev[i - 1] != NEG_INF)
{
cht.add(-pre[i - 1], dp_prev[i - 1], i - 1);
}
if (i >= t && !cht.empty())
{
auto res = cht.query(suf[i + 1]);
dp_cur[i] = res.first + suf[i + 1] * pre[i];
par[t][i] = res.second;
}
}
for (int i = 0; i <= n; ++i)
dp_prev[i] = dp_cur[i];
}
long long ans = NEG_INF;
int pos = 0;
for (int i = k; i <= n - 1; ++i)
{
if (dp_prev[i] > ans)
{
ans = dp_prev[i];
pos = i;
}
}
cout << ans << "\n";
int cur = pos;
for (int t = k; t >= 1; --t)
{
trace.push_back(cur);
if (t > 1)
cur = par[t][cur];
}
reverse(trace.begin(), trace.end());
for (int v : trace)
cout << v << " ";
}
