#include <bits/stdc++.h>
using namespace std;
#define int long long
#define aaa 100003
// #define aaa 1003
int arr[aaa] ;
int dp[2][aaa] ;
signed lst[203][100003] ;
int ps[aaa] ;
int n,k ;
void dc(int x,int l,int r,int ql,int qr){
int md=(l+r)/2 ;
int i,j ;
for (i = ql ; i <= min(md-1,qr) ; i ++){
dp[(x)%2][md]=max(dp[(x)%2][md],dp[(x+1)%2][i]+(ps[n]-ps[md])*(ps[md]-ps[i])) ;
}
for (i = ql ; i <= qr ; i ++){
if (dp[(x)%2][md]==dp[(x+1)%2][i]+(ps[n]-ps[md])*(ps[md]-ps[i])){
lst[x][md]=i ;
break ;
}
}
if (l==r) return ;
if (md-1>=l) dc(x,l,md-1,ql,i) ;
if (md+1<=r) dc(x,md+1,r,i,qr) ;
}
signed main() {
int i,j ;
cin >> n >> k ;
for (i = 1 ; i <= n ; i ++) cin >> arr[i],ps[i]=ps[i-1]+arr[i] ;
// for (i = 0 ; i < 203 ; i ++) for (j = 0 ; j < 100003 ; j ++) dp[i][j]=-LLONG_MAX/2 ;
for (j = 0 ; j < aaa ; j ++) dp[0][j]=-LLONG_MAX/2 ;
dp[0][0]=0 ;
for (i = 1 ; i <= k ; i ++){
for (j = 0 ; j < aaa ; j ++) dp[i%2][j]=-LLONG_MAX/2 ;
dc(i,1,n,0,n) ;
}
int mx=0 ;
for (i = 0 ; i <= n ; i ++) mx=max(mx,dp[k%2][i]) ;
cout << mx << endl ;
for (i = 0 ; i <= n ; i ++){
if (mx==dp[k%2][i]){
vector <int> v ;
int a=i,b=k ;
while (b!=0){
v.push_back(a) ;
a=lst[b][a] ;
b-- ;
}
reverse(v.begin(),v.end()) ;
for (auto x : v) cout << x << " " ; cout << endl ;
return 0 ;
}
}
return 0;
}
