#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define all(x) (x).begin(),(x).end()
#define Sort(x) sort(all((x)))
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define SZ(x) ll(x.size())
ll poww(ll a, ll b, ll md) {
return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const ll MAXN = 1e5 + 10;
const ll MAXK = 210;
const ll LOG = 22;
const ll INF = 2e18;
const ll MOD = 2e9 + 7; // 998244353; // 1e9 + 9;
ll n , k , ptr , A[MAXN] , ps[MAXN] , dp[2][MAXN];
int prv[MAXK][MAXN];
vector<pair<pll , pll>> vec;
ll insect(pll A , pll B){
ll x = B.Y - A.Y , y = A.X - B.X;
if(A.X == B.X) return (A.Y <= B.Y ? -MOD : MOD);
if(y < 0) y *= -1 , x *= -1;
return (x / y + (x % y > 0));
}
void insert(ll A , ll B , ll ind){
ll pos = -MOD;
while(SZ(vec)){
ll x = insect(vec.back().Y , pll(A , B));
pos = max(x , vec.back().X.X);
if(x > vec.back().X.X) break;
vec.pop_back();
}
if(SZ(vec)) assert(pos > vec.back().X.X);
ptr = min(ptr , max(0ll , SZ(vec) - 1));
vec.push_back({{pos , ind} , {A , B}});
}
pll get(ll pos){
ptr = min(ptr , max(0ll , SZ(vec) - 2));
while(ptr + 1 < SZ(vec) && vec[ptr + 1].X.X <= pos) ptr++;
return {vec[ptr].Y.X * pos + vec[ptr].Y.Y , vec[ptr].X.Y};
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> k;
for(int i = 1 ; i <= n ; i++){
cin >> A[i];
ps[i] = ps[i - 1] + A[i];
}
//cout << (-2 / 3) << endl;
//cout << (-2 % 3) << endl;
for(int i = 1 ; i <= k ; i++){
for(int j = 1 ; j <= n ; j++){
insert(ps[j - 1] , dp[1 - i % 2][j - 1] - ps[j - 1] * ps[j - 1] , j - 1);
pll A = get(ps[j]);
dp[i % 2][j] = A.X;
prv[i][j] = A.Y;
}
vec = {}; ptr = 0;
}
cout << dp[k % 2][n] << endl;
vector<int> ans;
int cur = prv[k][n] , ind = k - 1;
while(cur){
ans.push_back(cur);
cur = prv[ind][cur];
ind--;
}
reverse(all(ans));
for(int i : ans) cout << i << sep;
return 0;
}
/*
*/
