#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
char c;
bool nega=0;
while((!isdigit(c=getchar()))&&(c!='-'));
if(c=='-'){
nega=1;
c=getchar();
}
x=c-48;
while(isdigit(c=getchar())) x=x*10+c-48;
if(nega) x=-x;
}
template <typename T> inline void writep(T x){
if(x>9) writep(x/10);
putchar(x%10+48);
}
template <typename T> inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
writep(x);
}
template <typename T> inline void writeln(T x){
write(x);
putchar('\n');
}
#define taskname "sequence"
#define sqr(x) ((x)*(x))
int n, k;
ll a[100001];
ll s[100001];
ll f[100001];
int trace[100001][201];
const ll inf=mask(60);
class line{
public:
int a;
ll b;
///f(x)=ax+b;
line(int _a, ll _b){
a=_a;
b=_b;
}
line(){}
ll first_better(line L){///a>=L.a
if(a==L.a){
if(L.b<=b) return 0;
else return inf;
}
else{
if(L.b<=b) return 0;
return (L.b-b-1)/(a-L.a)+1;
}
}
};
class data{
public:
line L;
int id;
int first;
data (line _L, int _id, int _first){
L=_L;
id=_id;
first=_first;
}
};
deque <data> q;
void track(int nn, int k){
if(nn==0) return;
track(trace[nn][k], k-1);
if(nn==n) return;
write(nn);
putchar(' ');
}
int main(){
#ifdef Kanikou
if(fopen(taskname".inp", "r"))
freopen(taskname".inp", "r", stdin);
#endif // Kanikou
read(n);
read(k);
FOR(i, 1, n) read(a[i]);
FOR(i, 1, n) s[i]=s[i-1]+a[i];
FOR(i, 1, n) f[i]=-mask(60);
f[0]=0;
ll a;
FOR(j, 0, k){
q.clear();
q.pb(data(line(0, 0), 0, 0));
FOR(i, 1, n){
line add=line(s[i], f[i]-sqr(s[i]));
while((q.size()>1)&&(q[1].first<=s[i])) q.pop_front();
f[i]=s[i]*q.front().L.a+q.front().L.b;
trace[i][j]=q.front().id;
while((!q.empty())){
a=add.first_better(q.back().L);
if(a>=s[n]) break;
if(a<=q.back().first) q.pop_back();
else{
q.pb(data(add, i, min(a, s[n])));
break;
}
}
if(q.empty()) q.pb(data(add, i, 0));
}
}
writeln(f[n]);
track(n, k);
}
