#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

int N;
int ai[1010];
long long memo[1010][1010];
int mm2[1010][1010];
long long res;
long long Neg=-1000000000ll*1000000000;
long long Neg2=-2000000000ll*1000000000;
int num[1010];
int numL;
int mm3[1010][1010];

long long srch(int ll, int rr)
{
	int i, j;
	if(ll==3 && rr==5)
		int oo = 1;
	if(memo[ll][rr] != Neg)
		return memo[ll][rr];
	if(ll == rr)
		return ai[ll];
	if(ll+1==rr)
		return Neg2;
	if( (rr-ll+1)%2==0)
		return Neg2;
	long long mx=Neg2;
	long long tmp1, tmp2;
	int mxi, mxi2;
	int mxt;
	i = rr;
	long long tmx=Neg2;
	int tmxi;
	while(i-2>=ll){
		tmp1 = srch(i, rr);
		if(tmp1 > tmx){
			tmx = tmp1;
			tmxi = i;
		}
		tmp2 = srch(ll, i-2);
		if(tmp2+tmx > mx){
			mx = tmp2+tmx;
			mxi = (i-2+tmxi)/2;
			mxt = (tmxi-(i-2))/2;
		}
		i -= 2;
	}
	/*for(i=ll+1; i<rr; i++){
		for(j=1; j<=rr-i&&j<=i-ll; j++){
			tmp1 = srch(ll, i-j);
			tmp2 = srch(i+j, rr);
			if(tmp1!=Neg2 && tmp2!=Neg2)
				if(mx < tmp1+tmp2){
					mx = tmp1+tmp2;
					mxi = i;
					mxt = j;
				}
		}
	}*/
	/*if( (rr-ll+1) % 2 == 1){
		if(ai[ll]+ai[rr] > mx){
			mx = ai[ll]+ai[rr];
			mxi = (ll+rr)/2;
			mxt = 1;
		}
	}*/
	memo[ll][rr] = mx;
	mm2[ll][rr] = mxi;
	mm3[ll][rr] = mxt;
	return mx;
}

void srch2(int ll, int rr, int st)
{
	int i;
	if(ll==rr)
		return ;
	int p = mm2[ll][rr];
	//if(mm3[ll][rr] == 0){
	//srch2(ll, p-1, st);
	//srch2(p+1, rr, st+2);
	//num[numL] = st+1;
	//numL ++;
	int j = mm3[ll][rr];
	srch2(ll, p-j, st);
	srch2(p+j, rr, st+1+(j-1)+j);
	for(i=mm3[ll][rr]; i>=1; i--){
		num[numL] = i+st;
		numL ++;
	}
	/*}
	else{
		for(i=(ll+rr)/2; i>=1; i--){
			num[numL] = st+i;
			numL ++;
		}
	}*/
}

int srch12(vector<int> vi, int dep)
{
	int i, j;
	//for(i=0; i<vi.size(); i++)
	//	printf("%d ", vi[i]);
	//printf("\n");
	if(numL==dep){
		if(vi.size() != 1)
			return 0;
		if(vi[0] != res)
			return 0;
		return 1;
	}
	vector<int> vi2;
	if(num[dep]==0){
		for(i=1; i<vi.size(); i++)
			vi2.push_back(vi[i]);
		return srch12(vi2, dep+1);
	}
	if(num[dep]==vi.size()-1){
		for(i=0; i<vi.size()-1; i++)
			vi2.push_back(vi[i]);
		return srch12(vi2, dep+1);
	}
	if(num[dep]>0 && num[dep]<vi.size()-1){
		i = num[dep];
		for(j=0; j<i-1; j++)
			vi2.push_back(vi[j]) ;
		int tmp = vi[i-1] + vi[i+1];
		vi2.push_back(tmp) ;
		for(j=i+2; j<vi.size(); j++)
			vi2.push_back(vi[j]);
		return srch12(vi2, dep+1);
	}
	return 0;
}

int judge()
{
	int i;
	vector<int> vi;
	for(i=0; i<N; i++)
		vi.push_back(ai[i]);
	return srch12(vi, 0);
}

void solve()
{
	int i, j;
	for(i=0; i<N; i++)
		for(j=0; j<N; j++)
			memo[i][j] = Neg;
	res = srch(0, N-1);
	if(res != Neg2){
		numL = 0;
		srch2(0, N-1, 0);
	}
	long long tmp;
	int l2=-1, r2;
	//for(i=1; i<N; i++){
	for(i=0; i<N; i++){
		for(j=i; j<N; j++){
			tmp = srch(i, j);
			if(tmp > res){
				res = tmp;
				l2 = i;
				r2 = j;
			}
		}
	}
	if(l2!=-1){
		numL = 0;
		//for(i=r2+1; i<N; i++){
		for(i=N-1; i>=r2+1; i--){
			num[numL] = i;
			numL ++;
		}
		for(i=0; i<l2; i++){
			num[numL] = 0;
			numL ++;
		}
		srch2(l2, r2, 0);
	}
	printf("%lld\n", res);
	//if(judge() == 0){
	//	printf("Wrong\n");
	//	solve();
	//}
	printf("%d\n", numL);
	for(i=0; i<numL; i++)
		printf("%d\n", num[i]+1);
}

int res2;
int chg[100];
void srch22(vector<int> vi, int dep)
{
	int i, j;
	if(vi.size() == 1){
		if(vi[0] > res2){
			res2 = vi[0];
			int oo = 1;
		}
		return ;
	}
	//for(i=0; i<vi.size(); i++)
	//	printf("%d ", vi[i]);
	//printf("\n");
	vector<int> vi2;
	for(i=1; i<vi.size(); i++)
		vi2.push_back(vi[i]);
	chg[dep] = 0;
	srch22(vi2, dep+1);
	vi2.clear();
	for(i=0; i<vi.size()-1; i++)
		vi2.push_back(vi[i]);
	chg[dep] = vi.size()-1;
	srch22(vi2, dep+1);
	vi2.clear();
	for(i=1; i<vi.size()-1; i++){
		for(j=0; j<i-1; j++)
			vi2.push_back(vi[j]) ;
		int tmp = vi[i-1] + vi[i+1];
		vi2.push_back(tmp) ;
		for(j=i+2; j<vi.size(); j++)
			vi2.push_back(vi[j]);
		chg[dep] = i;
		srch22(vi2, dep+1);
		vi2.clear();
	}
}

void solve2()
{
	int i;
	res2 = -1000000000;
	vector<int> vi;
	for(i=0; i<N; i++)
		vi.push_back(ai[i]);
	srch22(vi, 0);
}

void test1()
{
	int i;
	N = rand() % 8 + 4;
	for(i=0; i<N; i++)
		ai[i] = rand() % 1000 - 500;
	solve();
	solve2();
	if(res != res2){
		printf("Wrong\n");
		solve();
	}
}

void test()
{
	int i;
	for(i=0; i<200; i++)
		test1();
}

int main()
{
	//test();
	//freopen("in.txt", "r", stdin);
	int i;
	scanf("%d", &N);
	for(i=0; i<N; i++)
		scanf("%d", &ai[i]);
	solve();
	return 0;
}

Measured memory_bytes: 16128