#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> values;
int n;
vector<int> operations;
ll memo[2010];
bool done[2010];
ll dp(int a)
{
	if (done[a]) return memo[a];
	done[a] = 1;
	ll ans = 0;
	for (int i = a + 2; i < n; i+=2)
	{
		ans = max(ans, dp(i) + values[i]);
	}
	return memo[a] = ans;
}
void findoptimal(int a, int alreadygone)
{
	pair<ll, int> best = {0, 0};
	for (int i = a + 2; i < n; i+=2)
	{
		best = max(best, { dp(i) + values[i], i });
	}
	if (best.first)
	{
		int s = a-alreadygone;
		int e = best.second-alreadygone;
		while (s != e)
		{
			int mid = (s+e)/2;
			operations.push_back(mid+1);
			alreadygone+=2;
			e-=2;
		}
		findoptimal(best.second, alreadygone);
	}
	else
	{
		int sz = n-a;
		while (sz != 1)
		{
			operations.push_back(sz);
			sz--;
		}
	}
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		ll a;
		scanf("%lld", &a);
		values.push_back(a);
	}
	pair<ll, ll> best = { -2e15, 0 };
	for (int i = 0; i < n; i++)
	{
		best = max(best, { dp(i) + values[i], i });
	}
	//printf("%lld %d\n", best.first, best.second);
	for (int i = 0; i < best.second; i++)
	{
		operations.push_back(1);
	}
	findoptimal(best.second, best.second);
	printf("%lld\n%d\n", best.first, operations.size());
	for (auto a : operations) printf("%d\n", a);
}