#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <functional>
#define task ""
#define size() size() * 1ll
#define all(x) (x).begin(), (x).end()
#define allr(x, sz) (x) + 1, (x) + 1 + sz
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define numbit(x) __builtin_popcountll(x)
using namespace std;
const int N = 1e5 + 5;
const int M = 1e3 + 1;
const long long mod = 1e9 + 7;
const long long oo = 1e18 + 7;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
template<class t>
bool mini(t &x,t y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
template<class t>
bool maxi(t &x,t y) {
if (x < y) {
x = y;
return 1;
}
return 0;
}
void file() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen(task".inp", "r", stdin);
// freopen(task".out", "w", stdout);
return ;
}
int n, k;
int a[N], trace[N][202];
ll suf[N], pre[N];
void solve(int test = -1) {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
for (int i = n; i >= 1; i--) suf[i] = suf[i + 1] + a[i];
auto y = [&](array<ll, 3> &d, int x) -> int {
return d[0] * x + d[1];
};
auto inters = [&](array<ll, 3> &d, array<ll, 3> &d1) -> long double {
return (long double) (d1[1] - d[1]) / (d[0] - d1[0]);
};
deque<array<ll, 3>> dp1;
for (int i = 1; i <= n; i++) dp1.pb({-pre[i], pre[i] * suf[i + 1], i});
for (int z = 1; z <= k; z++) {
deque<array<ll, 3>> dp2;
for (int i = z + 1; i <= n; i++) {
while (dp1.size() >= 2 && y(dp1[0], suf[i + 1]) <= y(dp1[1], suf[i + 1])) dp1.pop_front();
int val = y(dp1.front(), suf[i + 1]) + pre[i] * suf[i + 1];
trace[i][z] = dp1.front()[2];
array<ll, 3> d = {-pre[i], val, i};
while (dp2.size() >= 2 && inters(d, dp2.back()) >= inters(dp2.back(), dp2[dp2.size() - 2])) dp2.pop_back();
dp2.pb(d);
}
dp1 = dp2;
}
cout << dp1.back()[1] << '\n';
while (k > 0) {
n = trace[n][k];
cout << n << ' ';
k--;
}
}
int32_t main() {
file();
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++) {
solve(i);
}
return 0;
}
/*
*/
