Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
A. Массив без локальных максимумов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ване попался на глаза подарок с какого-то его предыдущего дня рождения, это массив размера n из целых чисел от 1 до 200. Массив немного истрепался, и некоторые числа нельзя разобрать. Ваня помнит, что для любого числа в массиве хотя бы один из его соседей не меньше его, более формально:

a1a2,

anan1 и

aimax(ai1,ai+1) для всех i от 2 до n1.

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

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

В первой строке содержится одно число n (2n105) — длина массива.

Во второй строке содержится n целых чисел ai — элементы массива. При этом либо ai=1, либо 1ai200. ai=1 значит, что i-й элемент массива нельзя разобрать.

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

Выведите одно целое число — количество способов восстановить массив по модулю 998244353.

Примеры
Входные данные
3
1 -1 2
Выходные данные
1
Входные данные
2
-1 -1
Выходные данные
200
Примечание

В первом примере единственное возможное значение a2 — 2.

Во втором примере a1=a2, следовательно различных значений ровно 200, так как все восстановленные значения должны быть целыми числами от 1 до 200.