// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10, maxk = 210, mod = 1e9 + 7;
const ll inf = 1e18 + 10;
int a[maxn];
ll dp[maxn], divi[maxn], cst[maxn], sm[maxn], sm2[maxn];
int restore[maxk][maxn], bef[maxn];
ll f(int l, int r){
return 1ll * (sm[r] - sm[l-1]) * (sm[r] - sm[l-1]) - (sm2[r] - sm2[l-1]) + dp[l-1];
}
void solve(int l, int r, int L, int R){
if(l > r)
return;
int mid = (l+r) >> 1;
divi[mid] = inf;
int pos = -1;
for(int i = min(mid, R); i >= L; i--){
ll num = f(i, mid);
if(num < divi[mid])
divi[mid] = num, pos = i;
}
bef[mid] = pos - 1;
solve(l, mid-1, L, pos);
solve(mid+1, r, pos, R);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
int n, k;
cin >> n >> k;
++k;
for(int i = 1; i <= n; i++){
cin >> a[i];
sm[i] = sm[i-1] + a[i];
sm2[i] = sm2[i-1] + 1ll * a[i] * a[i];
}
for(int i = 1; i <= n; i++){
dp[i] = sm[i] * sm[i] - sm2[i];
}
for(int i = 2; i <= k; i++){
solve(1, n, 1, n);
memcpy(dp, divi, sizeof dp);
memcpy(restore[i], bef, sizeof bef);
}
ll ANS = (1ll * sm[n] * sm[n] - sm2[n] - dp[n]) / 2;
vector<int> v;
int tmp = n;
for(int i = k; i >= 2; i--){
tmp = restore[i][tmp];
v.PB(tmp);
}
reverse(v.begin(), v.end());
cout << ANS << "\n";
for(int x : v){
cout << x << " ";
}
return cout << endl, 0;
}
