Ване попался на глаза подарок с какого-то его предыдущего дня рождения, это массив размера $$$n$$$ из целых чисел от $$$1$$$ до $$$200$$$. Массив немного истрепался, и некоторые числа нельзя разобрать. Ваня помнит, что для любого числа в массиве хотя бы один из его соседей не меньше его, более формально:
$$$a_{1} \le a_{2}$$$,
$$$a_{n} \le a_{n-1}$$$ и
$$$a_{i} \le max(a_{i-1}, \,\, a_{i+1})$$$ для всех $$$i$$$ от $$$2$$$ до $$$n-1$$$.
Ваня не помнит массив и попросил вас найти количество различных способов восстановить массив. Восстановленные элементы массива также должны быть целыми числами от $$$1$$$ до $$$200$$$. Поскольку это число может быть довольно большим, выведите его по модулю $$$998244353$$$.
В первой строке содержится одно число $$$n$$$ ($$$2 \le n \le 10^{5}$$$) — длина массива.
Во второй строке содержится $$$n$$$ целых чисел $$$a_{i}$$$ — элементы массива. При этом либо $$$a_{i} = -1$$$, либо $$$1 \le a_{i} \le 200$$$. $$$a_{i} = -1$$$ значит, что $$$i$$$-й элемент массива нельзя разобрать.
Выведите одно целое число — количество способов восстановить массив по модулю $$$998244353$$$.
3
1 -1 2
1
2
-1 -1
200
В первом примере единственное возможное значение $$$a_{2}$$$ — $$$2$$$.
Во втором примере $$$a_{1} = a_{2}$$$, следовательно различных значений ровно $$$200$$$, так как все восстановленные значения должны быть целыми числами от $$$1$$$ до $$$200$$$.
Название |
---|