Tweak the Peak

Michael has a favourite kind of skyline: one clean peak, and absolutely no valleys.

You are given an array of $n$ distinct integers. You may rearrange its elements in any order.

In a rearranged array, an index $i$ is a peak if $2 \le i \le n - 1$ and both neighbours are strictly smaller: $a_{i-1} < a_i$ and $a_{i+1} < a_i$.

Similarly, an index $i$ is a valley if $2 \le i \le n - 1$ and both neighbours are strictly larger: $a_{i-1} > a_i$ and $a_{i+1} > a_i$.

Count the number of distinct rearrangements of the array that have exactly one peak and zero valleys.

Since the answer can be large, output it modulo $998244353$.

Input

The first line contains the integer $n$, the length of the array.

The second line contains $n$ integers: $a_1, a_2, \ldots, a_n$.

Output

Print the number of distinct rearrangements with exactly one peak and zero valleys, modulo $998244353$.

Constraints

• $1 \le n \le 2 \cdot 10^5$
• $1 \le a_i \le 10^9$
• All $a_i$ are distinct.

Example 1

3
1 2 3

2

Explanation

The valid rearrangements are $[1, 3, 2]$ and $[2, 3, 1]$.

Example 2

4
1 2 3 4

6

Example 3

5
10 20 30 40 50

14