#include <bits/stdc++.h>
using namespace std;
typedef long double ll;
#define MAXN 100005
#define MAXK 205
const ll INF = 1e18;
ll dp[MAXN][MAXK];
ll a[MAXN];
int opt[MAXN][MAXK];
struct lajn
{
ll k;
ll n;
int idx;
};
ll eval(lajn l,ll x){return l.k*x+l.n;}
ll presekx(lajn a,lajn b)
{
if(a.k==b.k)return INF;
return 1.00*(a.n-b.n)/(b.k-a.k);
}
deque <lajn> q;
lajn next_front()
{
lajn z = q.front();
q.pop_front();
lajn o = q.front();
q.push_front(z);
return o;
}
lajn next_back()
{
lajn z = q.back();
q.pop_back();
lajn o = q.back();
q.push_back(z);
return o;
}
int main()
{
ios_base::sync_with_stdio(false);
int n,k;
cin >> n >> k;
for(int i = 1; i <= n; i++)cin >> a[i],a[i]+=a[i-1];
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= k; j++)
{
dp[j][i]=-INF;
}
}
for(int i = 1; i <= n; i++)dp[0][i]=0LL;
for(int i = 1; i <= k; i++)
{
q.clear();
lajn zzz;
zzz.k=0;
zzz.n=0;
q.push_front(zzz);
for(int j = 1; j <= n; j++)
{
while(q.size()>1 && presekx(q.front(),next_front())<=a[j])q.pop_front();
if(q.size())dp[i][j]=q.front().k*a[j]+q.front().n,opt[i][j]=q.front().idx;
lajn now;
now.k=a[j];
now.n=-a[j]*a[j]+dp[i-1][j];
while(q.size()>2 && presekx(next_back(),q.front())>=presekx(q.front(),now))q.pop_back();
q.push_back(now);
}
}
cout << dp[k][n] << "\n";
int now = n;
while(k>0)
{
cout << opt[k][now] << " ";
now=opt[k][now];
k--;
}
return 0;
}
