Migrated from Lutece 3204 随机排列

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

排列是好东西。

随机化也是好东西。

好东西的结合是坏东西。

所以现在有一个长为 $n$ 随机排列 $p$。

$p$ 是坏的，定义一个排列 $q$ 是好的当且仅当 $\forall i (1\le i< n), \max_{j=1}^iq_j\neq\max_{j=1}^ip_j$。

求好排列的个数，对 $998244353$ 取模。

Input

第一行一个正整数 $n$，表示排列的长度。 第二行 $n$ 个正整数，表示随机排列 $p$。

Output

一行一个正整数，表示好排列的个数对 $998244353$ 取模的结果。

Samples

2
2 1

1

5
3 5 1 4 2

18

15
6 13 2 8 7 11 1 3 9 15 4 5 12 10 14

424488915

Constraints

$2\le n\le 2\times 10^5$

$p$ 在长为 $n$ 的排列中均匀随机。

只有不超过 $10$ 组测试数据。

Resources

2024 UESTC ICPC Training for Math