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)$