402838: GYM100917 E Extreme Permutations

Permutation of length n is called the sequence of n integers, containing each of integers between 1 and n exactly once. For example, (3, 4, 5, 1, 2) and (1, 2) are permutations, (1, 4, 3) and (2, 1, 3, 2) are not.

Lets call the permutation extreme, if for any two neighbor numbers in the permutation difference between them is not less than minimum of those 2 numbers. For example, permutation (3, 1, 2, 4) is extreme, because |3 - 1| ≥ min(3, 1), |1 - 2| ≥ min(1, 2) and |2 - 4| ≥ min(2, 4).

Given an odd n, calculate number of the extreme permutations of length n where positions of some integers are fixed.

First line of the input contains one integer n — length of permutation (1 ≤ n ≤ 27, n = 2k + 1 for some integer k).

Second line contains n integers p₁, p₂, ..., p_n (0 ≤ p_i ≤ n). If p_i is equal to 0, then i-th position is not fixed, otherwise on i-th position must stay p_i. You may assume that if p_i > 0 and p_j > 0 for 1 ≤ i, j ≤ n, i ≠ j, then p_i ≠ p_j.

Print one integer — number of the extreme permutations where all fixed elements are on their positions.

5
0 0 0 0 0

4

5
0 1 0 0 5

1