Valid DFS Sequence Reconstruction

Little Blue is studying depth-first search (DFS). He wrote the following C++ code:

void dfs(int rt, int deep, int fa) {
    a[++cnt] = deep;
    for (int i = head[rt]; i; i = e[i].next)
        if (e[i].to != fa) dfs(e[i].to, deep + 1, rt);
}

When performing dfs(root, 0, 0) on a rooted tree, a sequence of depths of the nodes visited is generated. The sequence has a length equal to the number of nodes in the tree, and the i-th number in the sequence is the depth of the i-th node visited in the DFS.

Little Blue considers a sequence valid if it can be obtained by running a DFS on some rooted tree as above. Now, you are given a sequence of n integers, where each integer is either -1 or a non-negative integer. Each occurrence of -1 is a placeholder that can be replaced by any non-negative integer. Your task is to count how many ways there are to replace each -1 so that the resulting sequence becomes a valid DFS depth sequence.

The DFS process works as follows. The DFS sequence is generated by simulating the recursive procedure. Notice that whenever a new value is recorded, it must be exactly one more than the depth of the current node's parent (after possibly backtracking). In other words, if at some point the DFS recursion has a call stack corresponding to a continuous sequence of depths [0, 1, 2, ..., k-1] (with k being the current stack size), then for the next number in the DFS sequence, one may pop 0 or more elements from the stack. Suppose you pop r (with 0 ≤ r < k) elements; the current top of the stack becomes k - r - 1, and the next number must equal (k - r - 1) + 1 = k - r. After that, the new number is pushed onto the stack, so the new stack size becomes (k - r) + 1.

More formally, let the given sequence be a₁, a₂, ..., a_n. The following conditions must hold for the sequence to be valid:

• a₁ must be 0.
• For each index i (2 ≤ i ≤ n), if the current DFS recursion has a stack of size k (i.e. the current node has depth k - 1), then there exists an integer r (0 ≤ r < k) such that a_i equals k - r, where r represents the number of pops (backtracks) before adding the next child.

Your task is to count the number of ways to replace each -1 with a non-negative integer so that these conditions are satisfied.

Note: When a position in the sequence is not -1, it is fixed and cannot be changed.

Latex Formula: $$\text{If current stack size is }k, \text{ then for some } r \text{ with }0\le r<k, \; a_{i} = k - r.$$

inputFormat

The input consists of two lines:

The first line contains a single integer (n) (the length of the sequence).

The second line contains (n) space-separated integers. Each integer is either -1 or a non-negative integer.

outputFormat

Output a single integer representing the number of ways to replace each -1 with a non-negative integer such that the sequence is a valid DFS depth sequence.

sample

3
0 1 1

1