## note

• 偶奇で分けて貪欲でよいことに気付かずDPをした
• ひとつ以上選ばなければいけないことによるコーナーケースが消えるのでそう悪くもない

## implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define REP3R(i, m, n) for (int i = int(n) - 1; (i) >= int(m); -- (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;

int main() {
// input
int n; scanf("%d", &n);
vector<ll> a(n); REP (i, n) scanf("%lld", &a[i]);

// solve
vector<ll> dp(n);
vector<int> parent(n, -1);
dp[0] = a[0];
REP3 (i, 1, n) {
dp[i] = a[i];
for (int j = i - 2; j >= 0; j -= 2) {
if (dp[i] < dp[j] + a[i]) {
dp[i] = dp[j] + a[i];
parent[i] = j;
}
}
}
int r = max_element(ALL(dp)) - dp.begin();
ll result = dp[r];
vector<int> path;
REP3R (i, r + 1, n) {
path.push_back(i);
}
while (true) {
int l = parent[r];
if (l == -1) break;
while (l != r) {
path.push_back((r + l) / 2);
r -= 2;
}
}
while (r != 0) {
path.push_back(0);
r -= 1;
}

// output
printf("%lld\n", result);
printf("%d\n", int(path.size()));
for (int i : path) {
printf("%d\n", i + 1);
}
return 0;
}