Ване попался на глаза подарок с какого-то его предыдущего дня рождения, это массив размера n из целых чисел от 1 до 200. Массив немного истрепался, и некоторые числа нельзя разобрать. Ваня помнит, что для любого числа в массиве хотя бы один из его соседей не меньше его, более формально:
a1≤a2,
an≤an−1 и
ai≤max(ai−1,ai+1) для всех i от 2 до n−1.
Ваня не помнит массив и попросил вас найти количество различных способов восстановить массив. Восстановленные элементы массива также должны быть целыми числами от 1 до 200. Поскольку это число может быть довольно большим, выведите его по модулю 998244353.
В первой строке содержится одно число n (2≤n≤105) — длина массива.
Во второй строке содержится n целых чисел ai — элементы массива. При этом либо ai=−1, либо 1≤ai≤200. ai=−1 значит, что i-й элемент массива нельзя разобрать.
Выведите одно целое число — количество способов восстановить массив по модулю 998244353.
3
1 -1 2
1
2
-1 -1
200
В первом примере единственное возможное значение a2 — 2.
Во втором примере a1=a2, следовательно различных значений ровно 200, так как все восстановленные значения должны быть целыми числами от 1 до 200.