#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn = 1e5 + 2, maxk = 200 + 3;
ll dp[3][maxn], ps[maxn], a[maxn], inf = 1e18;
int opt[maxk][maxn];
inline ll ch(ll x){
return x * (x - 1) / (ll)2;
}
void solve(int l, int r, int x, int y, int k){
if(l + 1 > r){
return;
}
int mid = (l + r) / 2;
dp[k & 1][mid] = inf;
for(int i = x; i < min(y, mid); i ++){
ll val = dp[(k - 1) & 1][i] + ch(ps[mid + 1] - ps[i + 1]);
if(val < dp[k & 1][mid]){
dp[k & 1][mid] = val;
opt[k][mid] = i;
}
}
//cout << mid << " " << k << " : " << dp[k][mid] << endl;
solve(l, mid, x, opt[k][mid] + 1, k);
solve(mid + 1, r, opt[k][mid], y, k);
}
int main(){
fast_io;
int n, k;
cin >> n >> k;
ll sum = 0;
for(int i = 0; i < n; i ++){
cin >> a[i];
ps[i + 1] = ps[i] + a[i];
sum += a[i];
}
for(int i = 0; i < n; i ++){
dp[1][i] = ch(ps[i + 1]);
opt[1][i] = -1;
}
for(int i = 2; i <= k + 1; i ++){
solve(0, n, 0, n, i);
}
//cout << "dp : " << dp[k + 1][n - 1] << endl;
cout << ch(sum) - dp[(k + 1) & 1][n - 1] << endl;
int x = opt[k + 1][n - 1];
int t = k + 1;
while(x != -1){
cout << x + 1 << " ";
t --;
x = opt[t][x];
}
return 0;
}
