/**
* IT'S YA BOI KOSEH!!
* 2026-04-15-07.59
**/
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define upb upper_bound
#define lwb lower_bound
#define FILE(task) freopen(task".inp","r",stdin);freopen(task".out","w",stdout);
#define int ll
typedef long long ll;
typedef long double lldb;
///--------------------------------------------------------------------------------///
//VARIABLES
const int INF = 1e18;
const int MAXN = 1e5 + 5;
int dp[MAXN][2];
int n, k;
int a[MAXN];
int opt[MAXN][205];
int pref[MAXN];
//FUNCTIONS
int cost(int l, int r)
{
return pref[l - 1] * (pref[r] - pref[l - 1]);
}
void compute(int j, int l, int r, int optl, int optr)
{
if (l > r) return;
int mid = (l + r) >> 1;
int cur = j % 2;
int pre = (j - 1) % 2;
pair<int, int> best = {-INF, -1};
for (int i = max(j, optl); i <= min(mid, optr); i++)
{
best = max(best, {dp[i - 1][pre] + cost(i, mid), i});
}
opt[mid][j] = best.second;
dp[mid][cur] = best.first;
compute(j, l, mid - 1, optl, opt[mid][j]);
compute(j, mid + 1, r, opt[mid][j], optr);
}
//PROCESS
void read()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
}
void solve()
{
for (int i = 1; i <= k; i++)
{
compute(i, 1, n, 1, n);
}
vector<int> ans;
int cur = n;
for (int i = k; i >= 1; i--)
{
cur = opt[cur][i] - 1;
ans.pb(cur);
}
sort(all(ans));
cout << dp[n][k % 2] << '\n';
for (int i : ans) cout << i << ' ';
}
//MAIN
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//FILE("test");
bool t_case = false;
int tCase = 1;
if (t_case) cin >> tCase;
while (tCase--)
{
read();
solve();
}
return 0;
}
