#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=100010;
const ll inf=4e18;
int n, k, P[MX][201];
ll S[MX], D[MX][2];
ll sq(ll x){ return x*x; }
void solve(int s, int e, int l, int r, int t){
if(e<s) return;
int m=(s+e)/2, &pos=P[m][t]; ll &d=D[m][t&1]; d=inf;
for(int i=l; i<=r && i<m; i++){
ll now=D[i][1-(t&1)]+sq(S[m]-S[i]);
if(d>now) d=now, pos=i;
}
solve(s,m-1,l,pos,t);
solve(m+1,e,pos,r,t);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>k;
for(int i=1, a; i<=n; i++)
cin>>a, S[i]=S[i-1]+a, D[i][0]=sq(S[i]);
for(int i=1; i<=k; i++)
solve(1,n,1,n,i);
cout<<(sq(S[n])-D[n][k&1])/2<<'\n';
stack<int> stk;
for(int i=k, pos=n; i>=1; i--){
pos=P[pos][i];
stk.push(pos);
}
while(!stk.empty()) cout<<stk.top()<<' ', stk.pop();
return 0;
}
