Трішки знань з криптографії нікому не завадить

Нещодавно професор Л. розробив спеціальний шифр, який ніхто не міг зламати. Антон вирішив особисто це перевірити і вирішив розшифрувати його самостійно. Він помітив, що перед кожним повідомленням була намальована невелика піраміда, та перестановка $p$ з $n$ елементів.

Після тривалого процесу обдумування він зрозумів, що кожне повідомлення мало різний шифр, що базувався на кількості різних перестановок $n$ елементів, для яких виконувались наступні умови:

• перестановка є пірамідальною.

• перестановка є лексикографічно меншою за $p$.

Ваше завдання полягає в тому, щоб для заданого $p$ знайти, скільки пірамідальних перестановок існує, які лексикографічно менші за $p$. Оскільки це число може бути занадто великим, виведіть його за модулем $998244353$.

Перестановка з $n$ елементів називається пірамідальною, якщо існує індекс $k$ $(1\le k\le n)$, такий що:

• для кожного $i$ ($1<i\le k$), $p_{i-1}<p_i$;

• для кожного $i$ ($k<i\le n$), $p_{i-1}>p_i$.

Послідовність цілих чисел $a_1,a_2,\dots ,a_n$ називається перестановкою, якщо послідовність містить кожне ціле число від $1$ до $n$ рівно один раз. Наприклад, $[1,5,3,4,2]$ — це перестановка. Однак $[1,3,4]$ не є (вона не містить $2$ і містить $4$, який не повинен з'являтися в послідовності), і $[1,2,2,3]$ також не є (вона містить $2$ двічі і не містить $4$).

Масив $a$ лексикографічно менший за масив $b$, якщо і тільки якщо виконується одна з наступних умов:

• $a$ є префіксом $b$, але $a\ne b$;

• на першій позиції, де відрізняються $a$ та $b$, масив $a$ має менший елемент, ніж масив $b$.

Вхідні дані

Перший рядок містить одне ціле число $n$ $(1\le n\le 10^6)$ — довжина перестановки.

Другий рядок містить $n$ цілих чисел $p_1,p_2,\dots ,p_n$ ($1\le p_i\le n$) — елементи перестановки.

Гарантується, що $p$ — це перестановка.

Вихідні дані

Виведіть одне ціле число — відповідь на завдання.

Приклади

Примітка

У першому прикладі існує $7$ пірамідальних перестановок, менших або рівних $p$:

1. $[1,2,3,4,5]\le [1,5,3,4,2]$

2. $[1,2,3,5,4]\le [1,5,3,4,2]$

3. $[1,2,4,5,3]\le [1,5,3,4,2]$

4. $[1,2,5,4,3]\le [1,5,3,4,2]$

5. $[1,3,4,5,2]\le [1,5,3,4,2]$

6. $[1,3,5,4,2]\le [1,5,3,4,2]$

7. $[1,4,5,3,2]\le [1,5,3,4,2]$

Але $[1,5,4,3,2]>[1,5,3,4,2]$.

У другому прикладі існує лише $1$ пірамідальна перестановка, менша або рівна $p$:

1. $[1,2,3]\le [1,2,3]$

Оцінювання

1. ($8$ балів): $n\le 10$;

2. ($7$ балів): $n\le 30$;

3. ($6$ балів): $n\le 60$;

4. ($11$ балів): $n\le 500$;

5. ($13$ балів): $n\le 10000$;

6. ($22$ балів): $n\le 10^5$;

7. ($33$ балів): без додаткових обмежень.