#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXK 205
typedef long long ll;
ll dp[MAXN][MAXK];
ll s[MAXN];
int opt[MAXN][MAXK];
struct lajn
{
ll k;
ll n;
int idx;
};
ll f(lajn a,ll x)
{
return a.k*x+a.n;
}
bool bad(lajn x,lajn y,lajn z)
{
return 1LL*(x.n - y.n)*(z.k - y.k) >= 1LL*(y.n - z.n)*(y.k - x.k);
}
lajn prev_back(deque <lajn> q)
{
lajn x = q.back();
q.pop_back();
lajn y = q.back();
q.push_back(x);
return y;
}
void calc(int idx,int n)
{
deque <lajn> q;
for(int i = 1; i <= n; i++)
{
while(1)
{
if(q.size()<=1)break;
lajn a=q.front();
q.pop_front();
lajn b=q.front();
if(f(a,s[i])<=f(b,s[i]))continue;
q.push_front(a);
break;
}
if(q.size())
{
dp[idx][i]=f(q.front(),s[i]);
opt[idx][i]=q.front().idx;
}
lajn a;
a.k=s[i];
a.n=-s[i]*s[i]+dp[idx-1][i];
a.idx=i;
while(q.size()>1 && bad(prev_back(q),q.back(),a))q.pop_back();
while(q.size() && a.k==q.front().k && a.n>q.front().n)q.pop_back();
q.push_back(a);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
cin >> s[i];
s[i]+=s[i-1];
}
for(int i = 1; i <= k; i++)
{
calc(i,n);
}
cout << dp[k][n] << "\n";
vector <int> qqqqq;
int now = n;
while(k > 0)
{
qqqqq.push_back(opt[k][now]);//cout << opt[k][now] << " ";
now=opt[k][now];
k--;
}
sort(qqqqq.begin(),qqqqq.end());
for(auto x:qqqqq)cout << x << " ";
return 0;
}
