#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define mp make_pair
#define random mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
template <typename T> using oset = tree <pair <T, T>, null_type, less <pair <T, T>>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename Container>
void Print(Container& container, int starting) {
auto Start = container.begin() + starting, End = container.end();
while (Start != End) cout << *(Start++) << " ";
cout << '\n';
}
template <typename T>
void print(T&& t) {cout << t << '\n';}
template <typename T, typename... Args>
void print(T&& t, Args&&... args) {
cout << t << " ";
print(forward<Args>(args)...);
}
const int32_t MAXN = 1e5 + 5, MAXK = 205;
int64_t a[MAXN], dp[2][MAXN], n;
int32_t par[MAXK][MAXN];
void compute(int32_t l, int32_t r, int32_t optl, int32_t optr, int32_t k)
{
if (l > r) return;
int32_t mid = (l + r) >> 1, row = k & 1;
pair <int64_t, int64_t> best = make_pair(-1, -1);
for (int64_t i = optl; i < min(mid, optr + 1); ++i) best = max(best, make_pair(dp[row ^ 1][i] + (a[n] - a[mid]) * (a[mid] - a[i]), i));
dp[row][mid] = best.first;
par[k][mid] = best.second;
int64_t opt = best.second;
compute(l, mid - 1, optl, opt, k);
compute(mid + 1, r, opt, optr, k);
}
inline void solve() {
int32_t k;
cin >> n >> k;
memset(a, 0, sizeof a);
for (int32_t i = 1; i <= n; ++i) {
cin >> a[i];
a[i] += a[i - 1];
}
for (int32_t i = 0; i <= k; ++i) {
for (int32_t j = 0; j <= n; ++j) {
par[i][j] = -1;
}
}
for (int32_t i = 0; i <= n; ++i) {
dp[0][i] = dp[1][i] = -1;
}
dp[0][0] = 0;
for (int32_t i = 1; i <= k; ++i) {
compute(0, n - 1, 0, n - 1, i);
}
pair <int64_t, int32_t> ans = mp(-1, -1);
for (int32_t i = 1; i <= n; ++i) {
ans = max(ans, mp(dp[k & 1][i], i));
}
print(ans.F);
vector <int32_t> seq(k + 1);
int32_t cur = k;
while (k && ans.S != -1) {
seq[cur--] = ans.S;
assert(ans.S >= 1 && ans.S <= n);
ans.S = par[k--][ans.S];
}
Print(seq, 1);
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
// cin >> T;
for (int test = 1; test <= T; ++test) {
// cout << "Case #" << test << ": ";
solve();
}
}
