#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
const ll oo = 3e18;
int n, k;
template <typename T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
namespace sub_1_2_3_4 {
void solve() {
vector<ll> a(n + 5), s(n + 5);
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = a[i] + s[i - 1];
}
vector<vl> dp(n + 5, vl(k + 5)), trace(n + 5, vl(k + 5));
for (int i = 2; i <= n; i++)
for (int l = 1; l <= k; l++)
for (int j = 1; j <= i - 1; j++) {
if (chmax(dp[i][l], dp[j][l - 1] + (s[i] - s[j]) * s[j])) {
trace[i][l] = j;
}
}
cout << dp[n][k] << '\n';
for (int i = n, j = k; j >= 1; j--) {
i = trace[i][j];
cout << i << ' ';
}
cout << '\n';
}
}
struct Line {
ll a, b, id;
Line() { a = 0; b = -oo; id = -1; }
Line(ll _a, ll _b, ll _id): a(_a), b(_b), id(_id) {}
ll operator()(ll x) { return a * x + b; }
};
struct Node {
Line line;
Node *left, *right;
Node() { left = right = nullptr; }
};
struct LCT {
Node *root;
LCT() { root = new Node; }
void update(Node* &node, ll l, ll r, Line line) {
if (l > r) return;
if (node == nullptr) node = new Node;
if (l == r) {
if (line(l) > node->line(l)) node->line = line;
return;
}
ll m = (l + r) / 2;
if (line.a < node->line.a) swap(line, node->line);
if (line(m) > node->line(m)) {
swap(line, node->line);
update(node->left, l, m, line);
}
else update(node->right, m + 1, r, line);
}
pair<ll,ll> get(Node* &node, ll l, ll r, ll x) {
if (l > r || node == nullptr) return {-oo, -1};
pair<ll,ll> cur = {node->line(x), node->line.id};
if (l == r) return cur;
ll m = (l + r) / 2;
if (x < m) return max(cur, get(node->left, l, m, x));
else return max(cur, get(node->right, m + 1, r, x));
}
void update(Line line) {
update(root, 0, 1e9, line);
}
pair<ll,ll> get(ll x) {
return get(root, 0, 1e9, x);
}
};
namespace sub_5_6 {
void solve() {
vector<ll> a(n + 5), s(n + 5);
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = a[i] + s[i - 1];
}
vector<LCT> lct(k + 5);
vector<vector<pair<ll,ll>>> dp(n + 5, vector<pair<ll,ll>>(k + 5));
for (int i = 1; i <= n; i++)
for (int l = 0; l <= k; l++) {
if (i >= 2 && l >= 1) {
dp[i][l] = lct[l - 1].get(s[i]);
}
lct[l].update(Line(s[i], - (s[i] * s[i]) + dp[i][l].first, i));
}
cout << dp[n][k].first << '\n';
for (int i = n, j = k; j >= 1; j--) {
i = dp[i][j].second;
cout << i << ' ';
}
cout << '\n';
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
if (n <= 1000) sub_1_2_3_4::solve();
else sub_5_6::solve();
}
