#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 10;
int n, k;
int a[maxN];
int trace[maxN][212];
ll dp[maxN][2];
ll pre[maxN];
struct TLine{
ll fi, se, idx;
};
inline ld intersect(const TLine &i, const TLine &j){
return ld(i.se - j.se) / ld(j.fi - i.fi);
}
inline ll cal(const TLine &i, int x){
return i.fi * x + i.se;
}
struct CHT{
deque <TLine> line;
vector <TLine> save;
void compile(int i){
if (save.size() <= i) return;
while (line.size() > 1 && (line.back().fi == save[i].fi
|| intersect(line.back(), line[line.size() - 2]) <= intersect(line.back(), save[i]))){
line.pop_back();
}
line.pb(save[i]);
}
void add(const TLine &i){
save.pb(i);
}
ll get(ll val, int i, int j){
while (line.size() > 1 && cal(line[0], val) <= cal(line[1], val)) line.pop_front();
trace[i][j] = line[0].idx;
return cal(line[0], val);
}
void clear(){
line.clear();
save.clear();
}
};
CHT S[2];
void Init(){
cin >> n >> k;
++k;
for (int i = 1; i <= n; ++i){
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
S[0].add({0, 0, 0});
for (int _ = 1; _ <= k; ++_){
int i = _ % 2;
S[i].clear();
for (int j = _; j <= n - (k - _); ++j){
S[i ^ 1].compile(j - _);
ll val = pre[n] - pre[j];
dp[j][i] = S[i ^ 1].get(val, j, _) + pre[j] * val;
TLine newline = {-pre[j], dp[j][i], j};
S[i].add(newline);
}
}
cout << dp[n][k % 2] << "\n";
while (trace[n][k]){
cout << trace[n][k] << " ";
n = trace[n][k];
--k;
}
}
signed main(){
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
//freopen(taskname".out", "w", stdout);
}
faster;
ll tt = 1;
//cin >> tt;
while (tt--){
Init();
}
}
