#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
int main() {
// ios::sync_with_stdio(0);
// // cin.tie(0);
// freopen("test_input.txt", "r", stdin);
// freopen("test_output.txt", "w", stdout);
int n,m;cin>>n>>m;
vector<ll> a(n,0);
vector<vector<ll>> dp(n,vector<ll>(2,0));
vii p(n,vi(m+1));
REP(i,0,n)cin>>a[i];
REP(i,1,n)a[i]+=a[i-1];
deque<int> q;
REP(j,1,m+1){
q.clear();
q.push_back(j-1);
REP(i,j,n){;
while(q.size()>1&&dp[q[0]][0]+(a[i]-a[q[0]])*a[q[0]]<=dp[q[1]][0]+(a[i]-a[q[1]])*a[q[1]])q.pop_front();
dp[i][1]=dp[q[0]][0]+(a[i]-a[q[0]])*a[q[0]];
p[i][j]=q[0];
int sz=q.size();
while(sz>1&&(dp[i][0]-a[i]*a[i]-dp[q[sz-1]][0]+a[q[sz-1]]*a[q[sz-1]])*(a[q[sz-2]]-a[q[sz-1]])<=(dp[q[sz-1]][0]-a[q[sz-1]]*a[q[sz-1]]-dp[q[sz-2]][0]+a[q[sz-2]]*a[q[sz-2]])*(a[q[sz-1]]-a[i])){
q.pop_back();
sz--;
}
q.push_back(i);
}
REP(i,0,n)dp[i][0]=dp[i][1];
}
cout<<dp[n-1][1]<<"\n";
int x=n-1;
for(int j=m;j>=1;j--){
cout<<p[x][j]+1<<" ";
x=p[x][j];
}
}
