#include<iostream>
#include<queue>
using namespace std;
const int size = 120;
int n, seq[size];
int d[size][size], p[size][size];
queue < int > intervalQueue;
void findInterval(int s, int e, int* nOfInterval){
	if(p[s][e] == -1){
		intervalQueue.push(e - s + 1);
		return;
	}
	else{
		findInterval(s, p[s][e], nOfInterval);
		findInterval(p[s][e] + 1, e, nOfInterval);
		(*nOfInterval)++;
	}
}
int main(void){

	cin>>n;
	for(int i = 0; i<n; i++){
		cin>>seq[i];
	}

	for(int interval = 1; interval <= n-1; interval++){
		for(int x = 0; x < n - interval; x++){
			int y = x + interval, max = 0, min = 999999, intervalValue, intervalPos = -1;
			
			
			for(int k = x; k <= y; k++){
				if(max < seq[k])max = seq[k];
				if(min > seq[k])min = seq[k];
			}
			intervalValue = max - min;
			//find intervalValue between xth and yth. only 1 interval.
			if(x + 1 < y - 1){
				for(int k = x + 1; k < y - 1; k++){
					if(intervalValue < d[x][k] + d[k+1][y]){
						intervalValue = d[x][k] + d[k+1][y];
						intervalPos = k;
					}
				}
			}
			//find intervalValue between xth and yth by using DP table. available more than 1 interval.
			d[x][y] = intervalValue;
			p[x][y] = intervalPos;
		}
	}
	//we only consider upper triangle of DP table. y is always greater than x.

	int intervalSum = d[0][n-1], intervalNum = 1;
	findInterval(0, n-1, &intervalNum);
	cout<<intervalSum<<endl;
	cout<<intervalNum<<endl;
	while(!intervalQueue.empty()){
		cout<<intervalQueue.front()<<" ";
		intervalQueue.pop();
	}

	return 0;
}