E. Экстремальные перестановки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановкой длины n называется последовательность из n чисел, в которой каждое из чисел от 1 до n встречается ровно 1 раз. Например, (3, 4, 5, 1, 2) и (1, 2) — перестановки, а (1, 4, 3) и (2, 1, 3, 2) — нет.

Назовем перестановку экстремальной, если для любых двух соседних чисел в перестановке разница между ними больше или равна минимальному из них. Например, перестановка

(3, 1, 2, 4)
является экстремальной, поскольку |3 - 1| ≥ min(3, 1), |1 - 2| ≥ min(1, 2) и |2 - 4| ≥ min(2, 4).

Ваша задача — посчитать количество экстремальных перестановок для некоторого нечетного n, в которых некоторые элементы зафиксированы.

Входные данные

В первой строке дано нечетное целое число n (1 ≤ n ≤ 27).

Во второй строке даны n чисел p1, p2, ..., pn (0 ≤ pi ≤ n). Если pi равно 0 — то на i-ой позиции может быть любое число, иначе i-ое число в рассматриваемых перестановках должно быть равно pi. Гарантируется, что если pi > 0 и pj > 0 для 1 ≤ i, j ≤ n, i ≠ j, то pi ≠ pj.

Выходные данные

Выведите одно число — количество искомых перестановок.

Примеры
Входные данные
5
0 0 0 0 0
Выходные данные
4
Входные данные
5
0 1 0 0 5
Выходные данные
1