Yana, Mino, White и Huzz — лучшие друзья.
Наконец закончив сложные задания тренера, Huzz заслужил отдых. Он обрёл его в один ленивый полдень, когда мир, казалось, замедлил свой бег, окутанный тёплой золотистой дымкой приближающихся сумерек. Лёгкий ветерок лишь слегка колыхал пылинки, танцующие в косых солнечных лучах, пробивающихся сквозь листву огромного дуба.
В этой сонной, уютной тишине Huzz нашёл перестановку в своей мягкой игрушечной акуле. Он решил ради забавы поделиться ею с друзьями.
Mino любит разделять. Он может разделить эту перестановку на несколько подотрезков.
Yana любит менять местами. Он может выбрать один подотрезок и поменять местами его максимальный и минимальный элементы.
А именно, они могут выполнять следующие два типа операций любое количество раз и в любом порядке:
- split: Выбрать один подотрезок длины больше $1$. Затем выбрать позицию внутри него и разделить его на два соседних подотрезка. Например, $(a_i, \dots, a_j)$ можно разделить на $(a_i, \dots, a_k)$ и $(a_{k+1}, \dots, a_j)$, где $i \le k < j$.
- swap: Выбрать один подотрезок и поменять местами его максимальный и минимальный элементы.
Выполнив произвольное количество операций, они останавливаются, и все получившиеся подотрезки объединяются в исходном порядке, образуя новую перестановку.
White любит считать. Ей интересно — сколько различных перестановок они могут получить?
Так как результат может быть очень большим, вам нужно лишь найти ответ по модулю $998\,244\,353$.
Формат входных данных
Первая строка входных данных содержит целое число $n$ ($1 \le n \le 500$) — длину перестановки.
Вторая строка содержит $n$ целых чисел $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), задающих саму перестановку. Гарантируется, что $\{a_n\}$ является перестановкой.
Формат выходных данных
Выведите одно целое число — количество различных перестановок, которые они могут получить, по модулю $998\,244\,353$.
Примеры
стандартный ввод
4 1 4 2 3
стандартный вывод
10
стандартный ввод
7 5 1 4 2 6 3 7
стандартный вывод
340
Примечание
В первом примере ниже приведены все возможные перестановки, которые они могут получить:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$