Permutation Rank with Modulo

Given an integer N and a permutation of numbers from 1 to N, find the lexicographical rank of the given permutation among all N! possible permutations. The rank is 1-indexed and the answer should be given modulo \(998244353\).

The lexicographical rank \(R\) of a permutation \(P\) can be computed as:

[ R = 1 + \sum_{i=1}^{N} \left(\text{# of unused elements smaller than } P_i\right) \times (N-i)!\quad (\text{mod } 998244353) ]

Note: It is guaranteed that the input array is a permutation of \(\{1, 2, \ldots, N\}\).

inputFormat

The first line contains an integer N, representing the size of the permutation. The second line contains N space-separated integers representing the permutation.

outputFormat

Output a single integer which is the rank of the given permutation modulo \(998244353\).

sample

3
1 2 3

1