#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 2e18 + 5;
int n, k;
const int N = 1e5 + 5;
const int K = 2e2 + 5;
int arr[N];
int sum[N];
ll dist[N];
int opt[K][N];
ll dp[N];
ll dp2[N];
ll calc(int l, int r) {
ll between = 1ll * sum[l - 1] * (sum[r] - sum[l - 1]);
ll ans = dist[r] - dist[l - 1] - 2 * between;
return ans;
}
void divide(int l, int r, int optl, int optr, int opt[]) {
if (r < l) {
return;
}
int m = (l + r) / 2;
opt[m] = optl;
dp2[m] = linf;
for (int i = optl; i <= min(m, optr); i++) {
if (dp[i - 1] + calc(i, m) < dp2[m]) {
dp2[m] = dp[i - 1] + calc(i, m);
opt[m] = i;
}
}
divide(m + 1, r, opt[m], optr, opt);
divide(l, m - 1, optl, opt[m], opt);
}
void dpdivide() {
fill(dp + 0, dp + n + 1, linf);
dp[0] = 0;
for (int j = 1; j <= k + 1; j++) {
divide(1, n, 1, n, opt[j]);
for (int i = 1; i <= n; i++) {
dp[i] = dp2[i];
}
dp[0] = linf;
}
}
void init() {
}
void input() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
//arr[i] = 10000;
}
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + arr[i];
dist[i] = dist[i - 1];
dist[i] += arr[i] * arr[i];
dist[i] += 2ll * arr[i] * sum[i - 1];
}
}
void solve() {
dpdivide();
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += arr[i];
}
ll ans = 1ll * sum * sum - dp[n];
cout << ans / 2 << endl;
stack<int> have;
int now = n;
for (int i = k + 1; i >= 2; i--) {
have.push(opt[i][now] - 1);
now = opt[i][now] - 1;
}
while (!have.empty()) {
cout << have.top() << ' ';
have.pop();
}
}
void output() {
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int number_of_testcases = 1;
//cin >> number_of_testcases;
while (number_of_testcases--) {
init();
input();
solve();
output();
}
return 0;
}
