// Bolatulu
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define int long long
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define F first
#define S second
#define md (tl+tr)/2
#define TL v+v,tl,mid
#define TR v+v+1,mid+1,tr
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
using namespace std;
int binpow(int a,int n,int M) {
if (n==0)
return 1;
if (n%2!=0)
return (a * binpow(a,n-1,M))%M;
int z=binpow(a,n/2,M);
return (z*z)%M;
}
int rnd() {
int x = rand() << 15;
return rand() ^ x;
}
struct target {
int l,r,x,y,ans;
};
bool cmp(target a, target b) {
if (a.l==b.l)
return a.r<b.r;
return a.l<b.l;
}
const ll INF = 1e18+9;
const int N = 2e5+7;
const int M = 1e9+7;
const ll HZ = 1e5;
const int MAX = INT_MAX;
const int MIN = INT_MIN;
const db pi = 3.141592653;
const int P=31;
int n,k,a[N],ps[N];
bool u[N];
int find_pos1(int val,int L,int R) {
int l=L,r=R;
while (l+1<r) {
int mid=(l+r)/2;
if (ps[mid]-ps[L]<=val+ps[R-1]-ps[mid])
l=mid;
else
r=mid;
}
if (l==L) {
return (ps[r] - ps[L]) * (val + ps[R - 1] - ps[r]);
} else if (r==R) {
return (ps[l] - ps[L]) * (val + ps[R - 1] - ps[l]);
} else
return max((ps[r] - ps[L]) * (val + ps[R - 1] - ps[r]),(ps[l] - ps[L]) * (val + ps[R - 1] - ps[l]));
}
void solve() {
cin >> n >> k;
set <int> v1,v2;
for (int i=1;i<=n;i++)
cin >> a[i],ps[i]=ps[i-1]+a[i];
v1.insert(0), v2.insert(n+1);
int ansum=0;
vector <int> ans;
for (int i=1;i<=k;i++) {
int mx=-INF,pos,pos1=-1;
for (int j=1;j<n;j++) {
if (u[j])
continue;
auto f=v1.upper_bound(j);
f--;
int z= *v2.lower_bound(j+1), x= *f;
if (z==j or x==j)
continue;
if (mx<(ps[j]-ps[x])*(ps[z-1]-ps[j])) {
mx=(ps[j]-ps[x])*(ps[z-1]-ps[j]);
pos=j;
pos1=-1;
} else if (mx==(ps[j]-ps[x])*(ps[z-1]-ps[j])) {
pos1=j;
}
}
if (pos1==-1) {
u[pos] = true;
v1.insert(pos), v2.insert(pos + 1);
ansum += mx;
ans.push_back(pos);
} else {
auto f=v1.upper_bound(pos1);
f--;
int z= *v2.lower_bound(pos1+1), x= *f;
if (find_pos1(mx,x,pos) >= find_pos1(mx,pos1,z)) {
u[pos] = true;
v1.insert(pos), v2.insert(pos + 1);
ansum += mx;
ans.push_back(pos);
} else {
pos=pos1;
u[pos] = true;
v1.insert(pos), v2.insert(pos + 1);
ansum += mx;
ans.push_back(pos);
}
}
}
cout << ansum << '\n';
for (auto now : ans)
cout << now << ' ';
}
signed main() {
// freopen("sequence.in", "r", stdin);
// freopen("sequence.out", "w", stdout);
kanagattandirilmagandiktarinizdan
int test = 1,count = 1;
// cin >> test;
while (test--) {
// cout << "Case " << count << ": ";
solve();
if (test)
cout << '\n';
count++;
}
return 0;
}
