#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, s;
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 (c.Y-a.Y)*(a.X-b.X)>=(b.Y-a.Y)*(a.X-c.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>=(int)L.size()) pnt = L.size()-1;
while(pnt<(int)L.size()-1&&L[pnt+1].X.X*x+L[pnt+1].X.Y>L[pnt].X.X*x+L[pnt].X.Y){
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 ii = 1; ii <= k; ii++){
pnt = 0;
L.clear();
for(int i = n-ii; i >= 1; i--){
add(mp(mp(S[i+1],F[(ii+1)%2][i+1]),i+1));
F[ii%2][i] = get(S[i],ii,i)-S[i]*S[i];
}
}
res = -1;
for(int i = 1; i <= n-1; i++){
if(maxi(res,F[k%2][i])){
s = i;
}
}
cout<<res<<'\n';
BackTrack(s,k);
return 0;
}
