After receiving the mission to produce the clone trooper for the Galactic Republic, the Kaminoans realized that issues in their cloning technology had resulted in clones of varying heights, even though they were all created from the same genetic template. They recognized that, in preparation for the Clone Wars, these soldiers needed to be arranged in order of height from shortest to tallest.

Initially, there are ~n~ clones lined up and numbered from ~1~ to ~n~, with the first clone having height ~h_1~, the second clone having height ~h_2~, ~\dots~, and the last clone having height ~h_n~. To rearrange the line, the Kaminoans perform the following operation an arbitrary number of times:

• Choose an index ~i~ (~1 \leq i \leq n~), and let ~j~ be the largest index such that ~j < i~ and ~h_j > h_i~. (Note that if ~j~ does not exist, this operation is not considered valid.)

• Swap the positions of clone ~i~ and clone ~j~ (and simultaneously swap ~h_i~ and ~h_j~).

Count the number of ways of rearranging clones such that, in the end, the heights of the ~n~ clones are arranged from shortest to tallest. Two ways of rearrangement are considered different if the number of operations is different or if there exists a position where the pair ~(i, j)~ is different. Since the result can be very large, you only need to output the remainder when it is divided by ~998244353~.

Input

The first line contains an integer ~n~ (~1 \leq n \leq 10^6~), the number of clones.

The next line contains ~n~ distinct positive integers ~h_1, h_2, \dots h_n~ (~1 \leq h_i \leq 10^9~), the heights of the clones.

Output

Print the single line with the number of ways of rearrangement modulo ~998244353~.

Sample Input 1

3
17 70 13

Sample Output 1

1

Sample Input 2

7
174 177 172 176 175 171 173

Sample Output 2

7567560