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

Input

3
1 2 3

Output

2

Explanation

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

Example 2

Input

4
1 2 3 4

Output

6

Example 3

Input

5
10 20 30 40 50

Output

14