#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 100;
const int mod = (int)1e9+7;
int n, k;
int a[maxn];
ll pref[maxn];
ll dp[maxn][202];
int p[maxn][202];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = pref[i-1] + a[i];
}
for(int i = 1; i <= n; i++) {
dp[i][0] = 0;
}
for(int it = 1; it <= k; it++) {
int j = 0;
for(int i = 1; i <= n; i++) {
while(j + 1 < i && dp[j][it-1] + (pref[i] - pref[j]) * pref[j] <= dp[j+1][it-1] + (pref[i] - pref[j+1]) * pref[j+1]) {
j++;
}
while(j - 1 >= 0 && dp[j][it-1] + (pref[i] - pref[j]) * pref[j] <= dp[j-1][it-1] + (pref[i] - pref[j-1]) * pref[j-1]) {
j--;
}
p[i][it] = j;
dp[i][it] = dp[j][it-1] + (pref[i] - pref[j]) * pref[j];
}
}
vector<int> cur;
int last = n;
for(int i = k; i >= 1; i--) {
last = p[last][i];
cur.push_back(last);
}
cout << dp[n][k] << "\n";
reverse(cur.begin(), cur.end());
for(int x: cur) cout << x << " ";
}
