#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Kmax = 205, Nmax = 1e5 + 5;
ll dp[2][Nmax];
int opt[Kmax][Nmax], S[Nmax], A[Nmax];
int n, k;
ll cost(int x, int y) { return (ll) (S[y] - S[x-1]) * (S[y] - S[x-1]); }
void divide(int K, int st, int dr, int L, int R)
{
int mid = (st + dr) / 2, i;
dp[K&1][mid] = 1e18;
for(i=L; i<=R && i<mid; ++i)
{
ll C = dp[(K&1)^1][i] + cost(i+1, mid);
if(C < dp[K&1][mid]) dp[K&1][mid] = C, opt[K][mid] = i;
}
if(st <= mid-1) divide(K, st, mid-1, L, opt[K][mid]);
if(mid+1 <= dr) divide(K, mid+1, dr, opt[K][mid], R);
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false);
int i;
cin >> n >> k;
for(i=1; i<=n; ++i)
{
cin >> A[i];
S[i] = S[i-1] + A[i];
}
for(i=1; i<=n; ++i) dp[0][i] = 1e18;
for(i=1; i<=k+1; ++i)
{
divide(i, i, n, 0, n-1);
int j;
for(j=0; j<i; ++j) dp[i&1][j] = 1e18;
}
cout << (cost(1, n) - dp[(k+1)&1][n]) / 2 << '\n';
vector<int> positions;
for(i=k+1; i>=2; --i)
{
positions.push_back(opt[i][n]);
n = opt[i][n];
}
for(i=k-1; i>=0; --i) cout << positions[i] << ' ';
return 0;
}
