#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 100001
#define MOD 1000000007
ll p[N];
ll dp[N][2];
int ans[N][200];
int t;
void dnc(int l, int r, int optl, int optr){
if(l > r) return;
int m = (l + r) >> 1;
int be = optl;
dp[m][1] = dp[be][0] + (p[m] - p[be]) * (p[m] - p[be]);
int lim = min(optr, m - 1);
for(int i = optl + 1; i <= lim; ++i){
ll w = dp[i][0] + (p[m] - p[i]) * (p[m] - p[i]);
if(dp[m][1] >= w){
dp[m][1] = w;
be = i;
}
}
ans[m][t] = be;
dnc(l, m - 1, optl, be);
dnc(m + 1, r, be, optr);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin>>n>>k;
for(int i = 1; i <= n; ++i){
cin>>p[i];
p[i] += p[i - 1];
}
for(int i = 1; i <= n; ++i)
dp[i][0] = p[i] * p[i];
for(t = 0; t < k; ++t){
dnc(1, n, 0, n - 1);
for(int j = 1; j <= n; ++j)
swap(dp[j][0], dp[j][1]);
}
cout<<(p[n] * p[n] - dp[n][0]) / 2<<'\n';
for(int i = k - 1; i >= 0; i--){
n = ans[n][i];
cout<<n<<' ';
}
}
