#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define S second
#define F first
//const int inf = 1e18;
const int N = 100005;
const ll inf = 1e18;
int n, y, k, par[N][205], k1;
ll a[N], b[N], pref[N], suma, dp[N][205];
bool cut[N][205], used[N];
vector<int> ans;
ll f(int i, int j, int m){
// cout << i << ' ' << j << ' ' << m << '\n';
// cout << dp[m][j - 1] << ' ' << (pref[i] - pref[m]) << ' ' << (pref[n] - pref[i]) << '\n';
return dp[m][j - 1] + (pref[i] - pref[m]) * (pref[n] - pref[i]);
}
main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
cin >> n >> k;
k1 = k;
k++;
for(int i = 1; i <= n; ++i){
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
for(int i = 0; i <= n; ++i){
for(int j = 2; j <= k; ++j){
dp[i][j] = -inf;
}
}
for(int i = 1; i <= n; ++i){
for(int j = 2; j <= k; ++j){
int l = 0, r = i - 1;
while(r - l > 2){
int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if(f(i, j, m1) < f(i, j, m2))
l = m1;
else
r = m2;
}
// cout << l << ' ' << r << '\n';
if(f(i, j, l) >= f(i, j, l + 1)) r = l;
else if(l + 1 < i) l++;
if(l + 1 < i && f(i, j, l) >= f(i, j, l + 1)) r = l;
else if(l + 1 < i) l++;
dp[i][j] = f(i, j, l);
if(dp[i][j - 1] > dp[i][j] && dp[i][j - 1] > dp[i - 1][j]){
par[i][j] = par[i][j - 1];
cut[i][j] = cut[i][j - 1];
dp[i][j] = dp[i][j - 1];
}
else if(dp[i][j] > dp[i - 1][j]) {
cut[i][j] = 1;
par[i][j] = l;
}
else{
dp[i][j] = dp[i - 1][j];
par[i][j] = i - 1;
}
// cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
}
}
cout << dp[n][k] << '\n';
int ind = n;
while(ind != 0){
if(cut[ind][k]) {
ans.pb(ind);
used[ind] = 1;
ind = par[ind][k];
k--;
}
else ind = par[ind][k];
}
reverse(ans.begin(), ans.end());
ind = 1;
// cout << ans.size() << '\n';
while(ans.size() < k1){
// cout << ans.size() << ' ' << ind << '\n';
while(used[ind]) ind++;
ans.pb(ind);
used[ind] = 1;
}
for(auto to : ans){
cout << to << ' ';
}
}
