Кафе

#pragma GCC optimize("03")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <ctime>
#include <chrono>
#include <random>
#include <functional>
#include <stack>
//#include <windows.h>
//void* operator new(size_t size) {
//    if (void* ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
//    throw std::bad_alloc{};
//}
//void operator delete(void* ptr) {
//    HeapFree(GetProcessHeap(), 0, ptr);
//}

using namespace std;
using ll = long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using vst = vector<string>;
#define all(x) x.begin(), x.end()
#define size(x) int(x.size())
#define rep(x) for(int rep_i = 0; rep_i < x; ++rep_i)
#define forp(i, s, f) for(int i = s; i < f; ++i)
#define form(i, s, f) for(int i = s; i > f; --i)
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define elif else if
#define dprint(x) for (auto now: x) cout << now << '\n'

const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const int INF = 2e9 + 7;
const ll LINF = 1e18 + 7;
const double EPS = 1e-9;
const long double PI = acosl(-1.0);

void solve() {
    int n;
    cin >> n;
    vint sp(n);
    int cnt = 0;
    forp(i, 0, n) {
        cin >> sp[i];
        if (sp[i] > 100) cnt++;
    }
    vector<vint> dp(n + 1, vint(cnt + 1, INF));
    vector<vint> prev(n + 1, vint(cnt + 1, 0));
    dp[0][0] = 0;
    prev[0][0] = 0;
    forp(i, 0, n) {
        forp(j, 0, cnt + 1) {
            if (dp[i][j] != INF) {
                if (dp[i][j] + sp[i] < dp[i + 1][j]) {
                    dp[i + 1][j] = dp[i][j] + sp[i];
                    prev[i + 1][j] = 0;
                }
                if (sp[i] > 100) {
                    if (dp[i][j] + sp[i] < dp[i + 1][j + 1]) {
                        dp[i + 1][j + 1] = dp[i][j] + sp[i];
                        prev[i + 1][j + 1] = -1;
                    }
                }
                if (j > 0) {
                    if (dp[i][j] < dp[i + 1][j - 1]) {
                        dp[i + 1][j - 1] = dp[i][j];
                        prev[i + 1][j - 1] = 1;
                    }
                }
            }
        }
    }
    int mn = INF, acnt = 0;
    forp(j, 0, cnt + 1) {
        if (dp[n][j] <= mn) {
            mn = dp[n][j];
            acnt = j;
        }
    }
    cout << mn << '\n';
    vint path;
    int j = acnt;
    form(i, n, 0) {
        if (prev[i][acnt] == 1) {
            path.push_back(i);
        }
        acnt += prev[i][acnt];
    }
    reverse(all(path));
    cout << j << ' ' << size(path) << '\n';
    dprint(path);
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    /*cout << setprecision(x)*/
    cout << fixed;
    int t;
    t = 1;
    while (t > 0) {
        solve();
        t--;
    }
}