#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define MAXM 201
#define int long long
const int MIN = -1e9, MAX = 1e9;
struct Node {
pair<int, int> line;
int left, right;
Node() : line({0, -LLONG_MAX}), left(-1), right(-1) {}
};
class LiChaoTree {
private:
vector<Node> treeNodes;
unordered_map<int, int> lineIndex;
int minX, maxX;
int get(int x, pair<int, int> line) {
return line.first * x + line.second;
}
void update(int &nodeID, int l, int r, pair<int, int> line, int index) {
if (nodeID == -1) {
nodeID = treeNodes.size();
treeNodes.emplace_back();
}
Node &node = treeNodes[nodeID];
int mid = (l + r) / 2;
bool leftBetter = get(l, line) > get(l, node.line);
bool midBetter = get(mid, line) > get(mid, node.line);
if (midBetter) swap(node.line, line);
if (l == r) return;
if (leftBetter != midBetter)
update(node.left, l, mid, line, index);
else
update(node.right, mid + 1, r, line, index);
}
pair<int, int> query(int nodeID, int l, int r, int x) {
if (nodeID == -1) return {0, -LLONG_MAX};
Node &node = treeNodes[nodeID];
int mid = (l + r) / 2;
pair<int, int> bestLine = node.line;
if (x <= mid) {
pair<int, int> leftLine = query(node.left, l, mid, x);
if (get(x, leftLine) > get(x, bestLine)) bestLine = leftLine;
} else {
pair<int, int> rightLine = query(node.right, mid + 1, r, x);
if (get(x, rightLine) > get(x, bestLine)) bestLine = rightLine;
}
return bestLine;
}
public:
int root;
LiChaoTree(int minX, int maxX) : root(-1), minX(minX), maxX(maxX) {
treeNodes.reserve(MAXN * 4);
}
void addLine(pair<int, int> line, int index) {
update(root, minX, maxX, line, index);
lineIndex[line.first] = index;
}
int getMaxIndex(int x) {
pair<int, int> bestLine = query(root, minX, maxX, x);
return lineIndex.count(bestLine.first) ? lineIndex[bestLine.first] : -1;
}
void clear() {
treeNodes.clear();
lineIndex.clear();
root = -1;
}
};
int n, k;
int pref[MAXN], dp[2][MAXN], where[MAXM][MAXN];
LiChaoTree tree(MIN, MAX);
vector<int> ans;
int eval(pair<int, int> linija, int x) {
return linija.first * x + linija.second;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
pref[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> pref[i];
pref[i] += pref[i - 1];
}
for (int i = 1; i < n; i++)
dp[0][i] = pref[i] * (pref[n] - pref[i]);
for (int br = 2; br <= k; br++) {
for (int pos = br; pos < n; pos++) {
tree.addLine({pref[pos - 1], dp[0][pos - 1] - pref[pos - 1] * pref[n]}, pos - 1);
int bestIdx = tree.getMaxIndex(pref[pos]);
dp[1][pos] = pref[pos] * (pref[n] - pref[pos]) + eval({pref[bestIdx], dp[0][bestIdx] - pref[bestIdx] * pref[n]}, pref[pos]);
where[br][pos] = bestIdx;
}
for (int pos = br; pos < n; pos++)
dp[0][pos] = dp[1][pos];
tree.clear();
}
int maks = dp[0][k], pos = k;
for (int i = k + 1; i < n; i++) {
if (dp[0][i] > maks) {
maks = dp[0][i];
pos = i;
}
}
cout << maks << '\n';
ans.push_back(pos);
for (int i = k; i >= 2; i--) {
ans.push_back(where[i][pos]);
pos = where[i][pos];
}
reverse(ans.begin(), ans.end());
for (int x : ans) cout << x << " ";
cout << '\n';
return 0;
}
