#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, k;
ll dp[maxn][2];
ll prt[maxn];
int par[207][maxn];
void solve(int k, int l = 1 , int r = n , int ul = 1 , int ur = n){
if(l > r)return;
if(l == r){
for(int i = ul ; i <= ur and i < l ; i ++){
ll res = dp[i][!(k&1)];
res += (prt[l] - prt[i]) * (prt[n] - prt[l]);
if(res > dp[l][k&1]){
dp[l][k&1] = res;
par[k][l] = i;
}
}
}
int mid = (l + r) / 2;
for(int i = ul ; i <= ur and i < mid ; i ++){
ll res = dp[i][!(k&1)];
res += (prt[mid] - prt[i]) * (prt[n] - prt[mid]);
if(res >= dp[mid][k&1]){
dp[mid][k&1] = res;
par[k][mid] = i;
}
}
solve(k, l, mid - 1 , ul, par[k][mid]);
solve(k, mid + 1 , r , par[k][mid], ur);
}
int32_t main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> k;
for(int i = 1 ; i <= n ; i ++)
cin >> prt[i], prt[i] += prt[i - 1];
for(int i = 1 ; i <= k ; i ++)
solve(i , i , n-1 , i-1 , n-1);
int ans = 1;
for(int i = 1 ; i <= n ; i ++)if(dp[i][k&1] > dp[ans][k&1])ans = i;
cout << dp[ans][k&1] << endl;
cout << ans;
while(k > 1){
cout << ' ' << par[k][ans];
ans = par[k][ans] , k --;
}
return(0);
}
