#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}
ll check(vector<ll> a, vector<ll> ans) {
    each(x, ans) {
        assert(x < a.size());
        if (x == 0) a.erase(a.begin());
        else if (x+1 == a.size()) a.erase(a.begin()+x);
        else {
            a[x] = a[x-1] + a[x+1];
            a.erase(a.begin()+(x+1));
            a.erase(a.begin()+(x-1));
        }
    }
    assert(a.size() == 1);
    return a[0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n; cin >> n;
    vector<ll> a(n); cin >> a;
    bool all_neg = true;
    rep(i, n) {
        if (a[i] > 0) all_neg = false;
    }
    if (all_neg) {
        ll apos = 0;
        rep(i, n) if (a[i] > a[apos]) apos = i;
        vector<ll> ans;
        rrep(i, apos+1, n) ans.pb(i);
        rep(i, apos) ans.pb(0);
        cout << a[apos] << endl;
        cout << ans.size() << endl;
        each(x, ans) cout << x+1 << endl;
        exit(0);
    }
    // vector<vector<ll>> dp(n+1, vector<ll>(n+1, -linf));
    // rep(i, n) {
    //     dp[i][i+1] = a[i];
    // }
    // rep(w, 3, n+1) rep(l, n) {
    //     ll r = l + w;
    //     if (r > n) break;
    //     rep(m, l, r) {
    //         chmax(dp[l][r], dp[l][m] + dp[m+1][r]);
    //     }
    //     chmax(dp[l][r],
    // }
    // ll al = 0, ar = 1;
    // cout << dp[4][7] << endl;
    // rep(l, n+1) rep(r, n+1) {
    //     if (dp[l][r] > dp[al][ar]) {
    //         al = l, ar = r;
    //     }
    // }
    // cout << dp[al][ar] << endl;
    vector<vector<ll>> dp(n+1, vector<ll>(3, -linf));
    vector<vector<ll>> prv(n+1, vector<ll>(3, -1));
    vector<vector<bool>> sel(n+1, vector<bool>(3, false));
    dp[0][2] = 0;
    rep(i, n) rep(j, 3) {
        if (dp[i][j] < 0) continue;
        if (j == 0) {
            if (dp[i][j] + a[i] > dp[i+1][1]) {
                dp[i+1][1] = dp[i][j] + a[i];
                prv[i+1][1] = j;
                sel[i+1][1] = true;
            }
            if (dp[i][j] > dp[i+1][1]) {
                dp[i+1][1] = dp[i][j];
                prv[i+1][1] = j;
                sel[i+1][1] = false;
            }
        }
        else if (j == 1) {
            if (dp[i][j] > dp[i+1][0]) {
                dp[i+1][0] = dp[i][j];
                prv[i+1][0] = j;
                sel[i+1][0] = false;
            }
        }
        else {
            if (dp[i][j] > dp[i+1][j]) {
                dp[i+1][j] = dp[i][j];
                prv[i+1][j] = j;
                sel[i+1][j] = false;
            }
            if (dp[i][j] + a[i] > dp[i+1][1]) {
                dp[i+1][1] = dp[i][j] + a[i];
                prv[i+1][1] = j;
                sel[i+1][1] = true;
            }
        }
    }
    ll li = 0, lj = 0;
    rep(i, n+1) rep(j, 3) {
        if (dp[i][j] > dp[li][lj]) {
            li = i, lj = j;
        }
    }
    ll state = lj;
    vector<ll> selected;
    rrep(i, li) {
        if (sel[i+1][state]) {
            selected.pb(i);
        }
        state = prv[i+1][state];
    }
    sort(all(selected));
    vector<ll> ans;
    assert(selected.size() > 0);
    rrep(i, selected.back()+1, n) {
        ans.pb(i);
    }
    rrep(i, selected.size()-1) {
        ll d = selected[i+1] - selected[i] - 1;
        assert(d % 2 == 1);
        rep(j, (d+1)/2) {
            ans.pb(selected[i] + d/2 - j + 1);
        }
    }
    rep(i, selected.front()) {
        ans.pb(0);
    }
    vector<P> v;
    cout << dp[li][lj] << endl;
    // cout << selected << endl;
    cout << ans.size() << endl;
    each(x, ans) {
        cout << x+1 << endl;
    }
    // assert(dp[li][lj] == check(a, ans));
}


Measured memory_bytes: 512