#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
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 opt[N][K];
ll dp[N];
ll dp2[N];
int l = 1, r = 0;
int sum = 0;
ll cost = 0;
void add(int s) {
if (s == 0) {
l--;
cost += arr[l] * arr[l];
cost += 1ll * arr[l] * sum;
cost += 1ll * sum * arr[l];
sum += arr[l];
}
else {
r++;
cost += arr[r] * arr[r];
cost += 1ll * arr[r] * sum;
cost += 1ll * sum * arr[r];
sum += arr[r];
}
}
void rem(int s) {
if (s == 0) {
sum -= arr[l];
cost -= arr[l] * arr[l];
cost -= 1ll * arr[l] * sum;
cost -= 1ll * sum * arr[l];
l++;
}
else {
sum -= arr[r];
cost -= arr[r] * arr[r];
cost -= 1ll * arr[r] * sum;
cost -= 1ll * sum * arr[r];
r--;
}
}
void divide(int l, int r, int optl, int optr, int opt[]) {
if (r < l) {
return;
}
int m = (l + r) / 2;
for (int i = l; i <= m; i++) {
add(1);
}
opt[m] = optl;
dp2[m] = linf;
for (int i = optl; i <= min(m, optr); i++) {
if (dp[i - 1] + cost < dp2[m]) {
dp2[m] = dp[i - 1] + cost;
opt[m] = i;
}
rem(0);
}
for (int i = min(m, optr); i >= opt[m]; i--) {
add(0);
}
divide(m + 1, r, opt[m], optr, opt);
for (int i = opt[m] - 1; i >= optl; i--) {
add(0);
}
for (int i = m; i >= l; i--) {
rem(1);
}
divide(l, m - 1, optl, opt[m], opt);
}
void dpdivide() {
fill(dp + 0, dp + n + 1, linf);
dp[0] = 0;
for (int i = 1; i <= k + 1; i++) {
divide(1, n, 1, n, opt[i]);
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];
}
}
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; i >= 1; i--) {
have.push(opt[i][now]);
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;
}
