#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define MAXM 200
#define int long long
const int MIN=-1e9,MAX=1e9;
struct Node {
pair<int,int> line;
Node *left, *right;
bool active;
Node():line({0,-LLONG_MAX}),left(nullptr),right(nullptr),active(false){}
};
class LiChaoTree {
private:
Node* root;
int minX,maxX;
int get(int x,pair<int,int> line) {return line.first*x+line.second;}
void update(Node*& node,int l,int r,pair<int,int> line)
{
if (!node) node=new Node();
if (!node->active) {node->active=true;node->line=line;return;}
int mid=(l+r)/2;
bool leftBetter=get(l,line)>get(l,node->line);
bool midBetter=get(mid,line)>get(mid,node->line);
if (midBetter) swap(node->line,line);
if (l==r) return;
if (leftBetter!=midBetter) update(node->left,l,mid,line);
else update(node->right,mid+1,r,line);
}
pair<int,int> query(Node* node,int l,int r,int x)
{
if (!node or !node->active) return {0,-LLONG_MAX};
int mid=(l+r)/2;pair<int,int> bestLine=node->line;
if (x<=mid)
{
pair<int,int> leftLine=query(node->left,l,mid,x);
if (get(x,leftLine)>get(x,bestLine)) bestLine=leftLine;
}
else
{
pair<int,int> rightLine=query(node->right,mid+1,r,x);
if (get(x,rightLine)>get(x,bestLine)) bestLine=rightLine;
}
return bestLine;
}
void clear(Node* &node)
{
if (!node) return;
clear(node->left);clear(node->right);delete node;node=nullptr;
}
public:
LiChaoTree(int minX,int maxX):root(nullptr),minX(minX),maxX(maxX){}
void addLine(pair<int,int> line) {update(root,minX,maxX,line);}
pair<int,int> getMax(int x) {return query(root,minX,maxX,x);}
void clear(){clear(root);root=nullptr;}
};
int n,k;
int pref[MAXN],dp[2][MAXN],where[MAXM][MAXN];
map<pair<int,int>,int> mapa;
LiChaoTree tree(MIN,MAX);
vector<int> ans;
int eval(pair<int,int> linija,int x){return (long long)(linija.first*x)+linija.second;}
int32_t main()
{
cin>>n>>k;pref[0]=0;
for (int i=1;i<=n;i++) {cin>>pref[i];pref[i]+=pref[i-1];}
for (int i=1;i<=n;i++) dp[0][i]=(long long)(pref[i]*(pref[n]-pref[i]));
for (int br=2;br<=k;br++)
{
for (int pos=br;pos<n;pos++)
{
tree.addLine({pref[pos-1],dp[0][pos-1]-(long long)(pref[pos-1]*pref[n])});
mapa[{pref[pos-1],dp[0][pos-1]-(long long)(pref[pos-1]*pref[n])}]=pos-1;
pair<int,int> resenje=tree.getMax(pref[pos]);dp[1][pos]=(long long)(pref[pos]*(pref[n]-pref[pos]))+eval(resenje,pref[pos]);
where[br][pos]=mapa[resenje];
}
for (int pos=br;pos<=n;pos++) dp[0][pos]=dp[1][pos];
tree.clear();mapa.clear();
}
int maks=dp[0][k],pos=k;
for (int i=k+1;i<n;i++)
{
if (dp[0][i]>maks) {maks=dp[0][i];pos=i;}
}
cout<<maks<<endl;ans.push_back(pos);
for (int i=k;i>=2;i--) {ans.push_back(where[i][pos]);pos=where[i][pos];}
reverse(ans.begin(),ans.end());
for (int x:ans) cout<<x<<" ";
cout<<endl;return 0;
}
