#include<bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define Task "test"
#define ld long double
#define ll long long
#define X first
#define Y second
#define pb push_back
//#define Karma
using namespace std;
template <typename T> inline void Cin(T &x)
{
char c;
T sign = 1;
x = 0;
for (c = getchar(); c < '0' || c > '9'; c = getchar())
if (c == '-')
sign = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
x *= sign;
}
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
const int N = 1e5 + 7;
int n, k;
ll a[N], f[N], _f[N];
vector<int> p[210];
void Enter()
{
Cin(n), Cin(k);
For(i, 1, n) Cin(a[i]), a[i] += a[i - 1];
}
void DP(int g, int l, int r, int optl, int optr)
{
if(l > r) return;
int mid = (l + r) / 2, lim = min(optr, mid - 1);
f[mid] = -1;
For(i, optl, lim)
{
ll newcost = _f[i] + a[i] * (a[mid] - a[i]);
if(newcost > f[mid])
{
f[mid] = newcost;
p[g][mid] = i;
}
}
DP(g, l, mid - 1, optl, p[g][mid]);
DP(g, mid + 1, r, p[g][mid], optr);
}
void Solve()
{
For(i, 0, 200) p[i].resize(n + 1, 1);
For(i, 1, k)
{
DP(i, 1, n, 1, n);
For(j, 1, n) _f[j] = f[j];
}
cout << f[n] << '\n';
int ptr = n;
Ford(i, k, 1)
{
cout << p[i][ptr] << ' ';
ptr = p[i][ptr];
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef Karma
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
#endif // Karma
Enter();
Solve();
return 0;
}
