#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define MAXK 205
typedef long long ll;
ll a[MAXN];
ll opt[MAXN][MAXK];
ll dp[MAXN][MAXK];
const ll INF = 1e18;
struct line {ll k;ll n;int id;};
deque <line> q;
double presekx(line x,line y) {
if(x.k==y.k) return -1e18;
return 1.0*(x.n-y.n)/(y.k-x.k);
}
line next_front()
{
line x = q.front();
q.pop_front();
line y = q.front();
q.push_front(x);
return y;
}
line prev_back()
{
line x = q.back();
q.pop_back();
line y = q.back();
q.push_back(x);
return y;
}
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 j = 1; j <= k ;j++)
{
q.clear();
for(int i = 1; i <= n; i++)
{
while(q.size() >= 2 && presekx(q.front(),next_front()) <= a[i])q.pop_front();
if(q.size())
{
dp[j][i]=q.front().k*a[i]+q.front().n;
opt[j][i]=q.front().id;
}
line now;
now.k=a[i];
now.n=dp[j-1][i]-a[i]*a[i];
now.id=i;
while(q.size() >= 2 && presekx(prev_back(),q.back()) >= 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;
}
