#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
constexpr int NMAX = 1e5 + 5;
constexpr LL INF = 1LL * 1e18;
constexpr int KMAX = 205;
struct Dreapta {
LL a, b;
Dreapta (LL a_, LL b_) : a(a_), b(b_) {}
LL operator() (LL x) {
return x * a + b;
}
friend LD Intersect (const Dreapta &L1, const Dreapta &L2) {
LD numar = L2.b - L1.b;
LD numi = L1.a - L2.a;
return numar / numi;
}
};
typedef pair <Dreapta, int> PDI;
int N, K;
LL dp[NMAX][2];
LL sp[NMAX];
void Read () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
for (int i = 1; i <= N; ++ i ) {
int x;
cin >> x;
sp[i] = sp[i-1] + 1LL * x;
}
}
int bef[NMAX][KMAX];
void Solve () {
for (int j = 1; j <= K+1; ++ j ) {
int now = (j&1), old = (now^1);
deque <PDI> D;
for (int i = j; i <= N; ++ i ) {
Dreapta aux = Dreapta(sp[i-1], dp[i-1][old] - sp[i-1] * sp[N]);
while (D.size() >= 2 && Intersect(D[D.size()-2].first, D.back().first) >= Intersect(D.back().first, aux))
D.pop_back();
D.push_back({aux, i-1});
while (D.size() >= 2 && D.front().first(sp[i]) <= D[1].first(sp[i]))
D.pop_front();
dp[i][now] = D.front().first(sp[i]) + sp[i] * (sp[N] - sp[i]);
bef[i][j] = D.front().second;
}
}
int index = 0;
LL ans = -1;
for (int i = K; i < N; ++ i ) {
LL val = dp[i][(K&1)];
if (val > ans) {
ans = val;
index = i;
}
}
cout << ans << '\n';
cout << index << " ";
for (int i = K-1; i >= 1; -- i ) {
index = bef[index][i+1];
cout << index << " ";
}
}
int main () {
Read();
Solve();
return 0;
}
