#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define in insert
#define fi first
#define se second
#define vl vector<ll>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int sz = 2e5 + 123; /// mind this
const int MAX = 2e6 + 123;
const int BS = 61;
const ll inf = 1e17;
ll dp[2][sz], part[205][sz], p[sz], n;
bool cmp1(ll x, ll y, ll i){
ll canx = dp[0][x] + (p[i] - p[x]) * (p[n] - p[i]);
ll cany = dp[0][y] + (p[i] - p[y]) * (p[n] - p[i]);
return (canx <= cany);
}
bool cmp2(ll x, ll y, ll i){
ll c1 = (dp[0][y] - dp[0][x]) * (p[i] - p[y]);
ll c2 = (dp[0][i] - dp[0][y]) * (p[y] - p[x]);
return (c1 <= c2);
}
void solve(){
ll k, i, j;
cin >> n >> k;
vl v(n + 1);
for(i = 1; i <= n; i++){
cin >> v[i];
p[i] = p[i - 1] + v[i];
}
deque<ll> dq;
for(i = 1; i <= k; i++){
dq.pb(0);
for(j = 1; j <= n; j++){
while(dq.size() > 1 && cmp1(dq[0], dq[1], j)){
dq.pop_front();
}
ll cut = dq.front();
dp[1][j] = dp[0][cut] + (p[j] - p[cut]) * (p[n] - p[j]);
// cout << j << ' ' << cut << ' ' << dp[1][j] << endl;
part[i][j] = cut;
while(dq.size() > 1 && cmp2(dq[dq.size() - 2], dq.back(), j)){
dq.pop_back();
}
dq.pb(j);
}
dq.clear();
for(j = 1; j <= n; j++){
dp[0][j] = dp[1][j];
}
}
ll ans = -1, idx = -1;
for(i = 1; i <= n; i++){
if(dp[0][i] > ans){
ans = dp[0][i], idx = i;
}
}
cout << ans << endl;
for(i = k; i > 0; i--){
assert(idx);
cout << idx << ' ';
idx = part[i][idx];
}
cout << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
// cin >> t;
while(t--){
solve();
}
}
/*
7 3
4 1 3 4 0 2 3
*/
