#include <bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
using namespace std;
template<typename T> inline void read(T &x){
x = 0; char ch; while(!isdigit(ch=getchar()));
do{ x = 10*x+ch-'0'; } while(isdigit(ch=getchar()));
}
typedef long long ll;
typedef pair<ll,ll> pll;
const int N = 100001;
const int K = 201;
int n, k, Tr[K][N], pnt;
ll A[N], S[N], F[2][N], res;
vector<pair<pll,int> > L, D;
bool maxi(ll &x, ll y){
if(x<y) x = y;
else return 0;
return 1;
}
void BackTrack(int x, int d){
if(d==0) return;
cout<<x<<' ';
BackTrack(Tr[d][x],d-1);
}
bool bad(pll a, pll b, pll c){
return (a.Y-c.Y)*(b.X-a.X)<(a.Y-b.Y)*(c.X-a.X);
}
void add(pair<pll,int> p){
while(L.size()>=2&&bad(L[L.size()-2].X,L.back().X,p.X)){
L.pop_back();
}
L.push_back(p);
}
ll get(ll x, int d, int u){
if(pnt>=L.size()) pnt = L.size()-1;
while(pnt<L.size()&&L[pnt+1].X.X*x+L[pnt+1].X.second>L[pnt].X.X*x+L[pnt].X.second){
pnt++;
}
Tr[d][u] = L[pnt].Y;
return L[pnt].X.X*x+L[pnt].X.Y;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
read(n); read(k);
for(int i = 1; i <= n; i++){
read(A[i]);
S[i] = S[i-1]+A[i];
}
for(int i = 1; i <= n; i++){
F[1][i] = S[i]*(S[n]-S[i]);
D.push_back(mp(mp(S[i],F[1][i]),i));
}
for(int i = 0; i < n; i++) add(D[i]);
for(int ii = 2; ii <= k; ii++){
D.clear();
pnt = 0;
for(int i = 1; i <= n; i++){
F[ii%2][i] = get(S[i],ii,i)-S[i]*S[i];
D.push_back(mp(mp(S[i],F[ii%2][i]),i));
}
L.clear();
for(int i = 0; i < n; i++) add(D[i]);
}
res = -1;
int s;
for(int i = 1; i <= n; i++){
if(maxi(res,F[k%2][i])){
s = i;
}
}
cout<<res<<'\n';
BackTrack(s,k);
return 0;
}
