#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int MX = 100005;
int n, k;
int a[MX];
int sum[MX];
int pre[MX];
int cur[MX];
int32_t trace[MX][205];
void nhap(){
cin >> n >> k;
for(int i=1; i<=n; i++) cin >> a[i];
}
vector<pii> Line;
vector<int> id;
/// ax + b = ux + v;
/// ax - ux = v - b;
/// x(a - u) = (v - b)
/// x = (v - b)/(a - u);
bool bad(pii l1, pii l2, pii l3){
return (l2.se - l1.se)*(l2.fi - l3.fi) >= (l1.fi - l2.fi)*(l3.se - l2.se);
}
void addLine(pii cur, int idx){
while(Line.size() > 1 && bad(cur, Line.back(), Line[Line.size()-2])){
Line.pop_back();
id.pop_back();
}
Line.push_back(cur);
id.push_back(idx);
}
pii get(int x){
int res = (int)Line.size() - 1;
for(int lo=0, hi=(int)Line.size()-2; lo<=hi;){
int mid = (lo+hi)>>1;
if(x*(Line[mid].fi - Line[mid+1].fi)>=(Line[mid+1].se - Line[mid].se)) res = mid, hi = mid - 1;
else lo = mid + 1;
}
return {Line[res].fi*x + Line[res].se, id[res]};
}
void solve(){
for(int i=1; i<=n; i++) sum[i] = sum[i-1] + a[i];
for(int i=1; i<=n; i++) pre[i] = sum[i]*(sum[n] - sum[i]);
for(int j=2; j<=k; j++){
Line.clear();
id.clear();
addLine({-sum[j-1], pre[j-1]}, j-1);
for(int i=j; i<=n; i++){
pii tmp = get(sum[n] - sum[i]);
cur[i] = tmp.fi + sum[i]*(sum[n] - sum[i]);
trace[i][j] = tmp.se;
addLine({-sum[i], pre[i]}, i);
}
for(int i=1; i<=n; i++) pre[i] = cur[i], cur[i] = 0;
}
pii ans = {-1, 0};
for(int i=1; i<n; i++) ans = max(ans, {pre[i], i});
vector<int> path;
for(int u=ans.se, t=k; u!=0; u=trace[u][t], t--) path.push_back(u);
cout << ans.fi << endl;
reverse(path.begin(), path.end());
for(int &x: path) cout << x << ' ';
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
nhap();
solve();
return 0;
}
