#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e5 + 2, maxk = 202;
ll n, k, a, ps[maxn], dp[maxn][2], cur;
int track[maxn][maxk];
pair<ll, int> res = {0, 0};
vector<int> op;
struct Line
{
ll x, y;
int id;
};
deque<Line> hull;
bool check (const Line& A, const Line& B, const Line& C)
{
ll p = (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
return p >= 0;
}
void add (Line l)
{
while (hull.size() >= 2 && check(hull[hull.size() - 2], hull.back(), l))
hull.pop_back();
hull.push_back(l);
}
pair<ll, int> query (int q)
{
while (hull.size() >= 2 && hull.front().x*q + hull.front().y <= hull[1].x*q + hull[1].y) hull.pop_front();
return {hull.front().x*q + hull.front().y, hull.front().id};
}
int main ()
{
//freopen(task".INP", "r", stdin);
//freopen(task".OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a;
ps[i] = ps[i - 1] + a;
}
for (int i = 1; i < n; i++)
{
dp[i][1] = ps[i]*(ps[n] - ps[i]);
track[i][1] = i;
}
for (int j = 2; j <= k; j++)
{
hull.clear();
for (int i = 1; i < n; i++)
{
if (i > 1)
{
pair<ll, int> p = query(ps[i]);
dp[i][j & 1] = p.first + ps[i]*(ps[n] - ps[i]);
track[i][j] = p.second;
}
add({ps[i], dp[i][1 ^ (j & 1)] - ps[i]*ps[n], i});
}
}
for (int i = 1; i < n; i++) res = max(res, {dp[i][k & 1], i});
cur = res.second;
for (int j = k; j >= 1; j--)
{
op.push_back(cur);
cur = track[cur][j];
}
reverse(op.begin(), op.end());
cout << res.first << '\n';
for (int x : op) cout << x << " ";
}
