#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define int long long
#define ld long double
#define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e18 + 9;
const int MAX = 4000 + 5, LOGMAX = 20, B = 441, MOD = 998244353;
struct line{
int k, b;
int f(int x){
return x * k + b;
}
ld inter(line a){
return (ld)(a.b - b) / (ld)(k - a.k);
}
};
void solve(){
int n, k; cin >> n >> k;
k++;
int arr[n + 1];
int pre[n + 1];
pre[0] = 0;
for(int i = 1; i <= n; i++){
cin >> arr[i];
pre[i] = pre[i - 1] + arr[i];
}
vector<int> dp(n + 1, -oo);
dp[0] = 0;
//dp[i] = (dp[j] - pre[j] * pre[j]) + pre[i] * pre[j];
vector<int> par[k];
while(k--){
vector<int> ndp(n + 1, -oo);
par[k].resize(n + 1, 0);
deque<line> dq;
deque<int> id;
dq.push_back({0, dp[0]});
id.push_back(0);
for(int i = 1; i <= n; i++){
while(dq.size() >= 2 && dq[0].f(pre[i]) <= dq[1].f(pre[i])){
dq.pop_front();
id.pop_front();
}
ndp[i] = dq[0].f(pre[i]);
par[k][i] = id[0];
line a = {pre[i], dp[i] - pre[i] * pre[i]};
while(dq.size() >= 2 && ((dq.back().k == a.k && dq.back().b <= a.b) || (a.inter(dq[dq.size()-2]) >= dq.back().inter(dq[dq.size()-2])))){
dq.pop_back();
id.pop_back();
}
if(dq.back().k != a.k){
dq.push_back(a);
id.push_back(i);
}
}
swap(ndp, dp);
}
cout << dp[n] << '\n';
int i = n;
k = 0;
while(i != 0){
if(i != n) cout << i << ' ';
i = par[k++][i];
}
cout << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
}
