#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define mp make_pair
#define vec vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int INF = 1e18 + 127;
const ld EPS = 1e-5;
struct line {
ll k = 0, b = INF;
int id = -1;
line () {}
line (ll k, ll b, int id) : k(k), b(b), id(id) {}
inline ll operator () (const ll &x) { return k * x + b; }
};
struct cht {
vector <line> s;
vector <ld> pt;
inline ld cross (const line &a, const line &b) { return (ld)(b.b - a.b) / (ld)(a.k - b.k + EPS); }
inline void add (const line &x) {
while (sz(s) && cross(s.back(), x) <= pt.back()) s.pop_back(), pt.pop_back();
if (!sz(s)) pt.pb(-INF);
else pt.pb(cross(s.back(), x));
s.pb(x);
}
inline line get (const ll &x) { return s[upper_bound(all(pt), x) - pt.begin() - 1]; }
};
inline ll sqr (const ll &x) { return x * x; }
/// dp[i][k] = dp[j-1][k-1] + (p[i] - p[j-1]) * (s - p[i])
/// = (p[i]*s - p[i]*p[i]) + dp[j-1][k-1] - s*p[j-1] + p[i]*p[j-1]
inline void solve () {
int n, k; cin >> n >> k;
vector <ll> a (n + 1), p (n + 1);
ll sum = 0;
for (int i = 1; i <= n; ++i) cin >> a[i], sum += a[i];
for (int i = 1; i <= n; ++i) p[i] = p[i - 1] + a[i];
vector <vector <ll>> dp (n + 1, vector <ll> (k + 1));
vector <vector <int>> par (n + 1, vector <int> (k + 1));
for (int i = 1; i <= n; ++i) dp[i][1] = p[i] * (sum - p[i]);
for (int b = 2; b <= k; ++b) {
cht orz;
for (int i = 1; i <= b; ++i) {
orz.add(line(p[i - 1], dp[i - 1][b - 1] - sum * p[i - 1], i - 1));
}
for (int i = b; i <= n; ++i) {
line opt = orz.get(p[i]);
dp[i][b] = p[i] * sum - sqr(p[i]) + opt(p[i]);
par[i][b] = opt.id;
orz.add(line(p[i], dp[i][b - 1] - sum * p[i], i));
}
}
pair <ll, int> mx = {-1, -1};
for (int i = k; i <= n; ++i) umax(mx, {dp[i][k], i});
vector <int> res;
int og = mx.sc, ogg = k;
while (og > 0) {
res.pb(og);
og = par[og][ogg--];
}
reverse(all(res));
ll cst = 0, j = 0;
for (auto i : res) {
cst += (p[i] - p[j]) * (sum - p[i]);
j = i;
}
assert(cst == mx.fr);
cout << mx.fr << endl;
for (auto i : res) cout << i << " ";
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = 1; // cin >> t;
while (t--) solve();
return 0;
}
