#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
struct line
{
ll m, c; int idx;
ll val(ll x)
{
return (m*x + c);
}
};
int n, k;
const int N = 1e5 + 3;
const int K = 202;
ll dp[N][2];
int par[N][K];
ll s[N];
line hull[N];
int siz;
int ptr;
bool bad(int cur, int prev, int nxt)
{
line x, y, z;
y = hull[cur];
x = hull[prev];
z = hull[nxt];
return (y.c - x.c)*(y.m - z.m) >= (z.c - y.c)*(x.m - y.m);
}
void add(ll a, ll b, int id)
{
line n; n.m = a; n.c = b; n.idx = id; hull[siz++] = n;
while(siz >= 3 && bad(siz - 2, siz - 3, siz - 1))
{
hull[siz-2] = hull[siz-1];
siz--;
}
}
ll query(ll x)
{
if(ptr >= siz) ptr = siz - 1;
while(ptr < siz - 1 && hull[ptr].val(x) > hull[ptr+1].val(x))
{
ptr++;
}
return hull[ptr].val(x);
}
int a[N];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
ll sum = 0;
ll ans = 0;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
sum += a[i];
s[i] = s[i-1] + a[i];
dp[i][1] = s[i]*s[i];
}
for(int j = 2; j <= k + 1; j++)
{
for(int i = j; i <= n; i++)
{
ll x = -2*s[i-1];
ll y = dp[i-1][(j+1)&1] + s[i-1]*s[i-1];
add(x, y, i - 1);
ll tmp = query(s[i]);
dp[i][j&1] = tmp + s[i]*s[i];
par[i][j] = hull[ptr].idx;
}
siz = 0; ptr = 0;
}
int idx = n;
ans = dp[n][(k+1)&1];
ans = sum*sum - ans;
ans >>= 1;
cout << ans << "\n";
for(int i = k + 1; i >= 2; i--)
{
cout << par[idx][i] << " ";
idx = par[idx][i];
}
return 0;
}
