Matcom Online Grader

Juan likes permutations. He loves them so much that, whenever he is given a sequence of numbers, he generates a set with all possible permutations of that sequence. Now he wants to use the Bucket Sort algorithm to sort this huge set of permutations. To do so, he needs to know, for a given permutation $P$, how many permutations are lexicographically smaller than $P$.  Once he learns how to do this computation efficiently, Juan believes that he will be able to sort the huge set of permutations in no time. So he trusted you with this task: given a sequence $P$ of integers (not necessarily distinct), determine how many permutations of this sequence exist that are lexicographically smaller than $P$.

A permutation of a sequence $S$ is any rearrangement of the elements of $S$.

Let $P$ and $Q$ be two permutations of the same sequence of numbers. We say $P$ is lexicographically smaller than $Q$ if $P_i < Q_i$ where $i$ is the first index in which permutations $P$ and $Q$ differ. For example, permutation $(3, 2, 9, 2, 10)$ is lexicographically smaller than $(3, 2, 10, 2, 9)$.

In the first sample test case, the six permutations that are lexicographically smaller than $(3, 1, 2, 3)$ are: $(1, 2, 3, 3)$, $(1, 3, 2, 3)$, $(1, 3, 3, 2)$, $(2, 1, 3, 3)$, $(2, 3, 1, 3)$, and $(2, 3, 3, 1)$.

The first line of the input contains an integer $N$ $(1 \leq N \leq 200,000)$. The next line has $N$ positive integers $P_i$ $(1 \leq P_i \leq 10^9)$ representing the sequence $P$.

Print the number of permutations of the sequence $P$ that are lexicographically smaller than $P$, modulo the prime number $998244353$.