#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
const ll N = 1E5 + 10;
ll n, k;
ll a[N];
ll dp[N][2];
int pr[N][203];
ll j = 1;
void dac(ll l, ll r, ll L, ll R) {
if(l > r)return;
ll m = (l + r) >> 1ll;
for(int i = L; i <= min(R, m); i++) {
if(dp[m][1] <= dp[i - 1][0] + (a[m] - a[i - 1]) * a[i - 1])
dp[m][1] = dp[i - 1][0] + (a[m] - a[i - 1]) * a[i - 1],
pr[m][j] = i;
}
dac(l, m - 1, L, pr[m][j]);
dac(m + 1, r, pr[m][j], R);
}
int main() {
speed;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
a[i] += a[i - 1];
}
for(int p = 1; p <= k; p++) {
j = p;
dac(1, n, 1, n);
for(int i = 1; i <= n; i++)
dp[i][0] = dp[i][1], dp[i][1] = 0;
}
/*for(int j = 1; j <= n; j++) {
for(int p = k; p >= 1; p--) {
for(int i = j; i > p; i--) {
if(dp[j][p] < dp[i - 1][p - 1] + (a[j] - a[i - 1]) * a[i - 1])
dp[j][p] = max(dp[j][p], dp[i - 1][p - 1] + (a[j] - a[i - 1]) * a[i - 1]),
pr[j][p] = i;
}
}
}*/
cout << dp[n][0] << '\n';
vector<ll> vost;
ll x = n, y = k;
while(y) {
x = pr[x][y];
y--;
vost.pb(x);
x--;
}
reverse(vost.begin(), vost.end());
for(auto u : vost)
cout << u - 1 << " ";
}
/*
7 3
4 1 3 4 0 2 3
*/
