#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf 1000000000
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1 << j))
#define onbit(i, j) (i | (1 << j))
#define vi vector<int>
using namespace std;
int n, k;
int a[maxn];
int pre[maxn];
int sum(int l, int r)
{
return pre[r] - pre[l - 1];
}
namespace sub1
{
int solve(int l, int r, int k, vi &v)
{
if (k > r - l + 1)
return 0;
if (k == 0 or l == r)
return 0;
int ans = 0;
vi cc;
int pos = l, sl = 0;
fo(i, l, r - 1)
{
fo(j, 0, k - 1)
{
int val = solve(l, i, j, cc) + solve(i + 1, r, k - j - 1, cc) + sum(l, i) * sum(i + 1, r);
if (ans < val)
{
ans = val;
pos = i;
sl = j;
}
}
}
v.pb(pos);
solve(l, pos, sl, v);
solve(pos + 1, r, k - sl - 1, v);
return ans;
}
}
struct CHT
{
vector<pair<int,pii>> line;
int pos = 0;
void clear()
{
line.clear();
pos = 0;
}
int eval(pii a, int x)
{
return a.fi * x + a.se;
}
bool bad(pii a, pii b, pii c)
{
return (double)(b.se - a.se) / (a.fi - b.fi) <= (double)(c.se - a.se) / (a.fi - c.fi);
}
void add(pair<int,pii> newline)
{
line.pb(newline);
while (line.size() > 2 && bad(line[line.size() - 3].se, line[line.size() - 2].se, line.back().se))
line.erase(line.end() - 2);
}
pii get(int x)
{
if (pos >= line.size())
pos = line.size() - 1;
while (pos < line.size() - 1 && eval(line[pos].se, x) <= eval(line[pos + 1].se, x))
pos++;
return make_pair(eval(line[pos].se, x),line[pos].fi);
}
};
namespace full
{
CHT cht;
int dp[100010][2];
vi trace[100010][2];
void solve()
{
// fo(i, 0, k) cht[i].add({0, 0});
fo(j, 1, k)
{
cht.clear();
cht.add({0,{0, 0}});
fo(i, 1, n)
{
pii now = cht.get(pre[n] - pre[i]);
dp[i][j % 2] = now.fi + pre[i] * (pre[n] - pre[i]);
trace[i][j % 2] = trace[now.se][1 - j % 2];
if(now.se > 0)
trace[i][j % 2].pb(now.se);
// if(i == 4 and j == 3) cout << dp[i][j % 2] << "\n";
// if(i == 5 and j == 2) cout << now.se << "\n";
cht.add({i,{-pre[i], dp[i][1 - j % 2]}});
}
}
int pos = 0,res = 0;
fo(i,1,n) if(res < dp[i][k % 2])
{
pos = i;
res = dp[i][k % 2];
}
// cout << pos << "\n";
if(res == 0)
{
cout << res << "\n";
fo(i,1,k) cout << i << ' ' ;
return ;
}
cout << res;en;
for(int it : trace[pos][k % 2]) cout << it << ' ';
cout << pos;
// fo(i,0,k)
// cout << trace[n % 2][1 - k % 2][i] << ' ';en;
// if(trace[n % 2][1 - k % 2][i])
}
}
main()
{
#define name "TASK"
if (fopen(name ".inp", "r"))
{
freopen(name ".inp", "r", stdin);
freopen(name ".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
fo(i, 1, n)
{
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
// if (n <= 10)
// {
// vi v;
// cout << sub1::solve(1, n, k, v);
// en;
// sort(v.begin(), v.end());
// for (int it : v)
// cout << it << ' ';
// }
// else
full::solve();
}
