#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<stack>
#include<unordered_map>
#include<map>
#include<cstdio>
#define endl '\n'
#define ll long long
#define x first
#define y second
#define PII pair<int,int>
#define de(x) cout<<x<<endl
#define dee(x) cout<<x<<" "
#define mem(x,y) memset(x, y, sizeof x)
//#define double db
//#define int ll 
//#define double long double


using namespace std;
const int N = 100010, M = N * 2;
const ll mod = 1e9 + 7;
const ll mod1 = 983231753;

int n, k;
ll a[N],b[N];
ll f[N];
ll g[N];
ll sum[N];
int q[N];
int d[N][500];

ll X(int xx) { return sum[xx]; }
ll Y(int yy) { return g[yy] - sum[yy] * sum[yy]; }

int slope_up(int a, int b)
{
	return Y(a) - Y(b);
}

int slope_down(int a, int b)
{
	return X(a) - X(b);
}


//double slope(int i, int j)
//{
//	if (sum[i] == sum[j])
//	{
//		return -1e8;
//	}
//	return 1.0 * (Y(i) - Y(j)) / (X(i) - X(j));
//}

inline double slope(int u, int v) {
	if (sum[u] == sum[v])return -1e8;//attention!!!
	return 1.0 * ((1.0 * (Y(u) - Y(v))) / (1.0 * (X(u) - X(v))));
}

void solve()
{

	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + a[i];
	}


	for (int tim = 1; tim <= k; tim++)
	{
		int head = 1;
		int tail = 1;
		mem(q, 0);
		q[head] = 0;
		for (int i = 1; i <= n; i++)
		{
			while (head < tail && slope(q[head + 1], q[head]) >= -sum[i])
			{
				++head;
			}
			int j = q[head];
			f[i] = g[j] + sum[i] * sum[j] - sum[j] * sum[j];
			d[i][tim] = j;
			while (head < tail && slope(q[tail], q[tail - 1]) <= slope(i, q[tail])) --tail;
			q[++tail] = i;
		}
		for (int i = 1; i <= n; i++)
		{
			g[i] = f[i];
		}
	}
	cout << f[n] << endl;
	stack<int>ss;
	int p = n;
	int cnt = 0;
	while (p) {
		b[++cnt] = p;
		p = d[p][k];
		k--;
	}
	for (int i = cnt; i >= 2; i--)printf("%d ", b[i]);
}


signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}