#include<bits/stdc++.h>
#include<bits/stdc++.h>
#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <tuple>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <functional>
#include <numeric>
#include <iomanip>
#include <stdio.h>
#include <assert.h>
#include <cstring>
#define f first
#define s second
#define f first
#define s second
#define int long long
#define pii pair<int,int>
#define MAXV 200007
#define MAXE 100007
#define f first
#define s second
#define pii pair<int,int>
#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define drep(i,n) for(int i = n-1 ; i >= 0 ; i--)
#define crep(i,x,n) for(int i = x ; i < n ; i++)
#define lnf 3999999999999999999
#define inf 999999999
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)(c).size()
#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end())
using namespace std;
const int N = 1e5 + 5,K = 200;
int t,n,k,a[N],s[N],ans,bef[N][K + 5],last;
vector<pair<pii,int> > st[K + 5];
int f(int x,pii y) {
return y.f * x + y.s;
}
long double x_(pii x1,pii x2) {
return (x2.s - x1.s) / (x1.f - x2.f);
}
void add(int j,pii x,int i) {
while(st[j].size() > 1) {
pii cur = st[j].back().f;
pii prev = st[j][(int)st[j].size() - 2].f;
if(cur.f == x.f) {
st[j].pop_back();
continue;
}
if(x_(cur,x) <= x_(cur,prev)) st[j].pop_back();
else break;
}
st[j].push_back({x,i});
}
void query(int j,int c,int i) {
while(st[j].size() >= 2) {
pii cur = st[j].back().f;
pii prev = st[j][(int)st[j].size() - 2].f;
if(f(c,cur) > f(c,prev)) break;
st[j].pop_back();
}
if(!st[j].size()) return;
pii cur_ans;
cur_ans.s = f(c,st[j].back().f) - c * c;
cur_ans.f = c;
bef[i][j] = st[j].back().s;
add(j + 1,cur_ans,i);
if(j == k - 1) {
if(cur_ans.s > ans) {
ans = cur_ans.s;
last = i;
}
}
}
main(){
cin>>n>>k;
for(int i=1;i<=n;i++) {
cin >> a[i];
}
for(int i=n;i>=1;i--) {
s[i] = s[i+1] + a[i];
}
st[0].push_back({{s[1],0},1});
for(int i=2;i<=n;i++){
for(int j=k-1;j>=0;j--) {
query(j,s[i],i);
}
}
cout<<ans<<"\n";
int cur = k-1;
vector<int> ans;
while(cur >= 0) {
ans.push_back(last-1);
last = bef[last][cur];
cur--;
}
while(ans.size()) {
cout<<ans.back()<<" ",ans.pop_back();
}}
