Description

给定一个数字 $n$。

有三个数列 $a,b,c$，定义如下：

1. $a_1$ 到 $a_n$ 为包含 $1$ 到 $n$ 的排列，$a_{n+1}=n+1$。

2. $b_i$ 为 $a$ 中所有满足 $a_j\gt a_i,i\lt j$ 的 $j$ 的最小值。

3. $c_i$ 为 $a_1$ 到 $a_i$ 中最小的没有出现的正整数。

如果满足 $\sum_{i=1}^{n}(b_i+c_i)$ 取到最大值，则称 $a_1$ 到 $a_n$ 对应的排列是合法的。

现在给出一个 $1$ 到 $n$ 的合法排列，求它是字典序第几小的合法排列。

Format

Input

第一行一个数字 $n$。

第二行 $n$ 个数字，表示输入的排列。

Output

一个数字，表示答案。

由于答案可能过大，请对 $998244353$ 取模。

Samples

3
3 2 1

5

100
1 3 2 16 15 14 4 5 13 12 6 11 10 8 7 9 78 18 17 19 34 22 21 20 33 23 32 24 31 25 26 30 29 27 28 77 42 41 40 39 38 37 36 35 45 43 44 76 46 51 47 49 48 50 55 52 54 53 75 61 56 60 57 58 59 62 63 74 64 73 66 65 67 72 71 69 68 70 100 85 81 80 79 84 82 83 87 86 99 88 97 89 91 90 96 93 92 95 94 98

447845321

Limitation

$n\le 5\times10^5$