VODONCAY (VOI 2016)

#include <iostream>
#include <cstdio>
#define task "VODONCAY"
using namespace std;
using ll = long long;
using ld = long double;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

const int N = 4e6 + 2;
const int Inf = 1e9 + 7;
int n, par[N][2], parpar[N][2];
int a[N], dp[N][2];
int pre[N], suf[N];

template <typename T, typename V>
struct SegmentTree
{
    V st[N * 4];
    T s;
    int n;
    SegmentTree()
    {
    }
    void fill(const V &v)
    {
        fill_n(st, N * 4, v);
    }
    void Update(int id, int l, int r, const int &a, const V &v)
    {
        if (l > a || r < a)
            return;
        if (l == r && r == a)
        {
            st[id] = s.compare(st[id], v);
            return;
        }
        Update(id << 1, l, (l + r) / 2, a, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, a, v);
        st[id] = s.compare(st[id << 1], st[id << 1 | 1]);
    }
    void Update(int l, const V &v)
    {
        Update(1, 1, n, l, v);
    }
    V Get(int id, int l, int r, const int &a, const int &b)
    {
        if (l > b || r < a)
            return s.top;
        if (l >= a && r <= b)
            return st[id];
        return s.compare(Get(id << 1, l, (l + r) / 2, a, b),
                         Get(id << 1 | 1, (l + r) / 2 + 1, r, a, b));
    }
    V Get(int l, int r)
    {
        return Get(1, 1, n, l, r);
    }
};
struct Pair
{
    int x, y, z;
    Pair(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) {}
    bool operator<(const Pair &a) const
    {
        return x < a.x;
    }
};
struct mins
{
    int top = Inf;
    int compare(const int &a, const int &b)
    {
        return a < b ? a : b;
    }
};
struct maxs
{
    int top = -Inf;
    int compare(const int &a, const int &b)
    {
        return a > b ? a : b;
    }
};
struct minpair
{
    Pair top = Pair(Inf, 0, 0);
    Pair compare(const Pair &a, const Pair &b)
    {
        return a < b ? a : b;
    }
};

SegmentTree<mins, int> fpre;
SegmentTree<maxs, int> fsuf;
SegmentTree<minpair, Pair> f;

void Read()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

void Prepare()
{
    fsuf.n = fpre.n = n;
    fsuf.fill(-Inf);
    fpre.fill(Inf);
    for (int i = 1; i <= n; ++i)
    {
        pre[i] = i;
        int j = max(1, i - a[i] + 1);
        if (j < i)
            pre[i] = fpre.Get(j, i - 1);
        fpre.Update(i, pre[i]);
    }
    for (int i = n; i; --i)
    {
        suf[i] = i;
        int j = min(n, i + a[i] - 1);
        if (j > i)
            suf[i] = fsuf.Get(i + 1, j);
        fsuf.Update(i, suf[i]);
    }
    /*
    for (int i = 1; i <= n; ++i)
        cout << pre[i] << " ";
    cout << "\n";
    for (int i = 1; i <= n; ++i)
        cout << suf[i] << " ";
    cout << "\n";*/
}

void Trace(int i, int j)
{
    if (par[i][j] != 0)
        Trace(par[i][j], parpar[i][j]);
    cout << (j ? 1 : -1) * i << " ";
}

void Solve()
{
    f.n = n;
    f.fill(f.s.top);
    for (int i = 1; i <= n; ++i)
    {
        int x, y, z, t;
        /// 0 = [pre[i], i]
        /// 1 = [i, suf[i]]
        x = pre[i];
        y = i;
        z = i;
        t = suf[i];
        if (x == 1)
        {
            dp[i][0] = 1;
            if (z == 1)
            {
                dp[i][1] = 1;
                f.Update(t, Pair(dp[i][1], i, 1));
            }
            else
            {
                Pair s = f.Get(z - 1, n);
                if (s.x != Inf)
                {
                    dp[i][1] = s.x + 1;
                    par[i][1] = s.y;
                    parpar[i][1] = s.z;
                    f.Update(t, Pair(dp[i][1], i, 1));
                }
            }
            f.Update(y, Pair(dp[i][0], i, 0));
        }
        else
        {
            Pair s = f.Get(x - 1, n);
            if (s.x != Inf)
            {
                dp[i][0] = s.x + 1;
                par[i][0] = s.y;
                parpar[i][0] = s.z;
                if (z == 1)
                {
                    dp[i][1] = 1;
                    f.Update(t, Pair(dp[i][1], i, 1));
                }
                else
                {
                    Pair s = f.Get(z - 1, n);
                    if (s.x != Inf)
                    {
                        dp[i][1] = s.x + 1;
                        par[i][1] = s.y;
                        parpar[i][1] = s.z;
                        f.Update(t, Pair(dp[i][1], i, 1));
                    }
                }
                f.Update(y, Pair(dp[i][0], i, 0));
            }
            else
            {
                if (z == 1)
                {
                    dp[i][1] = 1;
                    f.Update(t, Pair(dp[i][1], i, 1));
                }
                else
                {
                    Pair s = f.Get(z - 1, n);
                    if (s.x != Inf)
                    {
                        dp[i][1] = s.x + 1;
                        par[i][1] = s.y;
                        parpar[i][1] = s.z;
                        f.Update(t, Pair(dp[i][1], i, 1));
                    }
                }
            }
        }
    }
    Pair s = f.Get(n, n);
    cout << s.x << "\n";
    Trace(s.y, s.z);
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Prepare();
    Solve();
}