E. Extreme Permutations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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 p1, p2, ..., pn (0 ≤ pi ≤ n). If pi is equal to 0, then i-th position is not fixed, otherwise on i-th position must stay pi. You may assume that if pi > 0 and pj > 0 for 1 ≤ i, j ≤ n, i ≠ j, then pi ≠ pj.

Output

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

Examples
Input
5
0 0 0 0 0
Output
4
Input
5
0 1 0 0 5
Output
1