Key observation：每个元素的下标奇偶性不改变。
于是讨论最后一个数是下标为奇数还是偶数加起来的数。将下标奇偶性相同的元素分开考虑。对于下标奇偶性相同的元素，不难发现答案的上界是所有 \(> 0\) 的元素之和（没有 \(> 0\) 的元素时选一个最大的），并且一定能够构造方案以达到上界。
例如，下面 O 代表对答案有贡献的元素，. 代表没有贡献的元素：
.O.O...O
方案是 .O.O...O \(\to\) O.O...O \(\to\) O...O \(\to\) O.O \(\to\) O。
因为 \(n \le 10^3\)，构造方案就直接模拟即可，复杂度 \(O(n^2)\)。
code
// Problem: E - Both Sides Merger
// Contest: AtCoder - AtCoder Regular Contest 092
// URL: https://atcoder.jp/contests/arc092/tasks/arc092_c
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1010;
ll n, a[maxn], t1, t2;
pii b[maxn], c[maxn], d[maxn], e[maxn];
vector<int> ans;
inline void work(int i) {
ans.pb(i);
if (i == 1) {
for (int i = 1; i < n; ++i) {
d[i] = d[i + 1];
}
--n;
} else if (i == n) {
--n;
} else {
int m = 0;
for (int j = 1; j <= n; ++j) {
if (abs(j - i) <= 1) {
if (j == i) {
e[++m] = make_pair(d[i - 1].fst + d[i].fst + d[i + 1].fst, d[i - 1].scd);
}
} else {
e[++m] = d[j];
}
}
n = m;
for (int i = 1; i <= n; ++i) {
d[i] = e[i];
}
}
}
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
if (i & 1) {
b[++t1] = make_pair(a[i], i);
} else {
c[++t2] = make_pair(a[i], i);
}
}
sort(b + 1, b + t1 + 1, greater<pii>());
sort(c + 1, c + t2 + 1, greater<pii>());
ll mx = -1e18, s = 0;
for (int i = 1; i <= t1; ++i) {
if (i > 1 && b[i].fst < 0) {
break;
}
s += b[i].fst;
mx = max(mx, s);
}
s = 0;
for (int i = 1; i <= t2; ++i) {
if (i > 1 && c[i].fst < 0) {
break;
}
s += c[i].fst;
mx = max(mx, s);
}
printf("%lld\n", mx);
s = 0;
for (int i = 1; i <= n; ++i) {
d[i] = make_pair(a[i], 0);
}
for (int i = 1; i <= t1; ++i) {
s += b[i].fst;
if (s == mx) {
for (int j = 1; j <= i; ++j) {
d[b[j].scd].scd = 1;
}
while (!d[1].scd) {
work(1);
}
for (int j = 2; j < n; ++j) {
if (j > 1 && d[j - 1].scd == d[j + 1].scd) {
work(j);
j -= 2;
}
}
while (!d[n].scd) {
work(n);
}
printf("%d\n", (int)ans.size());
for (int x : ans) {
printf("%d\n", x);
}
return;
}
}
s = 0;
for (int i = 1; i <= t2; ++i) {
s += c[i].fst;
if (s == mx) {
for (int j = 1; j <= i; ++j) {
d[c[j].scd].scd = 1;
}
while (!d[1].scd) {
work(1);
}
for (int j = 2; j < n; ++j) {
if (j > 1 && d[j - 1].scd == d[j + 1].scd) {
work(j);
j -= 2;
}
}
while (!d[n].scd) {
work(n);
}
printf("%d\n", (int)ans.size());
for (int x : ans) {
printf("%d\n", x);
}
return;
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}