#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
#define fi first
#define se second
const int MAXN = 1e4+5;
const int MAXK = 205;
int N, K;
ll data[MAXN], pref[MAXN], suff[MAXN];
ll dp[MAXK][MAXN], ans=0;
int tambah[MAXK][MAXN];
stack<int>putus;
void init(){
memset(data, 0, MAXN);
memset(pref, 0, MAXN);
memset(suff, 0, MAXN);
memset(dp, -1, sizeof dp);
memset(tambah, -1, sizeof tambah);
for(int i=0;i<MAXN;i++) dp[0][i] = 0, tambah[0][i] = 0;
for(int i=0;i<MAXK;i++) dp[i][0] = 0, tambah[i][0] = 0;
}
void bruteforce(int posK, int ind){
//cout << posK << " " << ind << ": ";
for(int l=posK-1;l<ind;l++){
ll tmp = dp[posK-1][l]+(pref[ind]-pref[l])*suff[ind+1];
//cout << tmp << " ";
if(dp[posK][ind] <= tmp){
dp[posK][ind] = tmp;
tambah[posK][ind] = l;
}
}
//cout << endl;
}
void bruteforce_search(int posK, int ind, int l, int r){
//cout << posK << " " << ind << ": ";
for(;l<=r;l++){
ll tmp = dp[posK-1][l]+(pref[ind]-pref[l])*suff[ind+1];
//cout << tmp << " ";
if(dp[posK][ind] <= tmp){
dp[posK][ind] = tmp;
tambah[posK][ind] = l;
}
}
//cout << endl;
}
void ternary_search_max(int posK, int ind){
int l = posK-1,
r = ind-1,
m_ans = l;
while(l <= r){
if(r-l <= 300){
bruteforce_search(posK, ind, l, r);
break;
}
ll m1 = l + (r-l)/3,
m2 = r - (r-l)/3;
// cout << posK << " " << ind << ": " << m1 << " " << m2 << endl;
ll res1 = dp[posK-1][m1]+(pref[ind]-pref[m1])*suff[ind+1],
res2 = dp[posK-1][m2]+(pref[ind]-pref[m2])*suff[ind+1];
if(res1 > res2){
r = m2-1;
m_ans = m1;
}else{
l = m1+1;
m_ans = m2;
}
}
// cout << posK << " " << ind << ": " << m_ans << endl;
// dp[posK][ind] = dp[posK-1][m_ans]+(pref[ind]-pref[m_ans])*suff[ind+1];
// tambah[posK][ind] = m_ans;
}
void binser_max(int posK, int ind){
int l = posK-1,
r = ind-1,
mid,
m_ans = l;
while(l < r){
mid = (l+r)/2;
ll f1 = dp[posK-1][mid]+(pref[ind]-pref[mid])*suff[ind+1],
f2 = dp[posK-1][mid+1]+(pref[ind]-pref[mid+1])*suff[ind+1];
if(f1 > f2){
r = mid+1;
m_ans = mid;
}else{
l = mid;
m_ans = mid+1;
}
}
dp[posK][ind] = dp[posK-1][m_ans]+(pref[ind]-pref[m_ans])*suff[ind+1];
tambah[posK][ind] = m_ans;
}
int main(){
init();
cin >> N >> K;
for(int i=1;i<=N;i++){
cin >> data[i];
pref[i] = data[i]+pref[i-1];
}
for(int i=N;i>0;i--){
suff[i] = suff[i+1]+data[i];
}
for(int j=1;j<N;j++){
ll tmp = pref[j]*suff[j+1];
//cout << j << " " << tmp << endl;
if(dp[1][j] <= tmp){
dp[1][j] = tmp;
tambah[1][j] = 0;
}
}
for(int i=2; i<=K; i++){
for(int j=1;j<N;j++){
if(j < i) continue;
//binser_max(i, j);
if(abs(i-j) > 300) ternary_search_max(i, j);
else bruteforce(i, j);
}
}
for(int i=1;i<N;i++) ans = max(ans, dp[K][i]);
int nxt,
cnt = K;
for(int i=N-1;i>0;i--){
if(ans == dp[cnt][i]){
putus.push(i);
nxt = tambah[cnt][i];
cnt--;
break;
}
}
while(nxt != 0){
putus.push(nxt);
nxt = tambah[cnt][nxt];
cnt--;
}
/*
for(int i=1;i<=K;i++){
for(int j=1;j<N;j++) cout << tambah[i][j] << " ";
cout << endl;
}
*/
cout << ans << endl;
cout << putus.top();
putus.pop();
while(!putus.empty()){
cout << " " << putus.top();
putus.pop();
}
cout << endl;
}
