#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = j; i < k; i++)
#define pb push_back
#define for_all(x) x.begin(), x.end()
constexpr int N = 1e5 + 10;
typedef long long ll;
typedef pair<int, int> pii;
typedef complex<long double> point;
template <typename S, typename T>
inline void smin(S &l, T r) {
l = l < r ? l : r;
}
int n, k;
ll dp[2][N], a[N], A[N], B[N];
int upt[N][202];
inline ll f(int l, int r) {
return B[r] - B[l - 1] - A[l - 1] * (A[r] - A[l - 1]);
}
void solve(int l, int r, int s, int t, int w) {
if (l >= r) return;
int mid = l + r >> 1;
dp[1][mid] = 2e18;
int id = s;
rep(i, s, min(mid, t)) {
ll val = dp[0][i] + f(i + 1, mid);
if (val < dp[1][mid]) {
dp[1][mid] = val;
id = i;
}
}
upt[mid][w] = id;
solve(l, mid, s, id + 1, w);
solve(mid + 1, r, id, t, w);
}
bool mark[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
rep(i, 1, n + 1) {
cin >> a[i];
A[i] = A[i - 1] + a[i];
B[i] = B[i - 1] + a[i] * A[i - 1];
dp[0][i] = 2e18;
}
rep(i, 0, k + 1) {
solve(1, n + 1, 0, n, i);
memcpy(dp[0], dp[1], (n + 1) * sizeof(long long));
}
cout << B[n] - dp[0][n] << endl;
vector<int> res;
int me = upt[n][k];
for (int i = k; i; i--) {
if (me) {
res.pb(me);
mark[me] = true;
}
me = upt[me][i - 1];
}
int ptr = 1;
while (res.size() < k) {
if (!mark[ptr]) res.pb(ptr);
ptr++;
}
for (auto e : res) cout << e << ' ';
return 0;
}
