#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<ll> a(n+1), prefix(n+1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
prefix[i] = prefix[i-1] + a[i];
}
// dp[i][j] = max points with i splits in first j elements
vector<vector<ll>> dp(k+1, vector<ll>(n+1, 0));
// opt[i][j] = position t of last split
vector<vector<int>> opt(k+1, vector<int>(n+1, 0));
for (int i = 1; i <= k; i++) {
int t = 0; // pointer to track optimal previous split
for (int j = 1; j <= n; j++) {
// Move t to the right while it improves dp[i][j]
while (t < j-1) {
ll curr = dp[i-1][t] + prefix[t]*(prefix[j]-prefix[t]);
ll next = dp[i-1][t+1] + prefix[t+1]*(prefix[j]-prefix[t+1]);
if (next >= curr) t++;
else break;
}
dp[i][j] = dp[i-1][t] + prefix[t]*(prefix[j]-prefix[t]);
opt[i][j] = t;
}
}
// Reconstruct split positions
vector<int> splits;
int curr_j = n;
int curr_i = k;
while (curr_i > 0) {
int t = opt[curr_i][curr_j];
splits.push_back(t);
curr_j = t;
curr_i--;
}
reverse(splits.begin(), splits.end());
cout << dp[k][n] << "\n";
for (int s : splits) cout << s << " ";
cout << "\n";
return 0;
}
