$n$ fishermen have just returned from a fishing vacation. The $i$-th fisherman has caught a fish of weight $a_i$.

Fishermen are going to show off the fish they caught to each other. To do so, they firstly choose an order in which they show their fish (each fisherman shows his fish exactly once, so, formally, the order of showing fish is a permutation of integers from $1$ to $n$). Then they show the fish they caught according to the chosen order. When a fisherman shows his fish, he might either become happy, become sad, or stay content.

Suppose a fisherman shows a fish of weight $x$, and the maximum weight of a previously shown fish is $y$ ($y = 0$ if that fisherman is the first to show his fish). Then:

  if $x \ge 2y$, the fisherman becomes happy;  if $2x \le y$, the fisherman becomes sad;  if none of these two conditions is met, the fisherman stays content. 

Let's call an order in which the fishermen show their fish emotional if, after all fishermen show their fish according to this order, each fisherman becomes either happy or sad. Calculate the number of emotional orders modulo $998244353$.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 5000$).

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$).


-----Output-----

Print one integer — the number of emotional orders, taken modulo $998244353$.


-----Examples-----
Input
4
1 1 4 9

Output
20

Input
4
4 3 2 1

Output
0

Input
3
4 2 1

Output
6

Input
8
42 1337 13 37 420 666 616 97

Output
19200

Difficulty: interview

Starter code:

Solutions:
from collections import defaultdict
import sys
input = sys.stdin.readline
n = int(input())
a = map(int, input().split())
mod = 998244353
d = defaultdict(int)
for x in a:
    d[x] += 1
d[0] = 0
b = list(d.items())
b.sort()
m = len(b)
ba = [0] * m
cn = [0] * (m + 1)
k = h = 0
for i, x in enumerate(b):
    while h < m and x[0] >= b[h][0] * 2:
        h += 1
    ba[i] = h - 1
    while k < m and x[0] * 2 > b[k][0]:
        k += 1
    cn[k] += x[1]
for i in range(m):
    cn[i+1] += cn[i]
dp = [0] * m
dp[0] = 1
b = [x[1] for x in b]
for i in range(n):
    ndp = [0] * m
    for j in range(1, m):
        if cn[j] >= i - 1:
            ndp[j] = dp[j] * (cn[j] - i + 1) % mod
        dp[j] += dp[j-1]
        if dp[j] >= mod:
            dp[j] -= mod
    for j in range(1, m):
        ndp[j] += dp[ba[j]] * b[j]
        ndp[j] %= mod
    dp = ndp
print(sum(dp) % mod)

from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
a = map(int, input().split())
mod = 998244353
d = Counter(a)
d[0] = 0
b = list(d.items())
b.sort()
m = len(b)
ba = [0] * m
cn = [0] * (m + 1)
k = h = 0
for i, x in enumerate(b):
    while h < m and x[0] >= b[h][0] * 2:
        h += 1
    ba[i] = h - 1
    while k < m and x[0] * 2 > b[k][0]:
        k += 1
    cn[k] += x[1]
for i in range(m):
    cn[i+1] += cn[i]
dp = [0] * m
dp[0] = 1
b = [x[1] for x in b]
for i in range(n):
    ndp = [0] * m
    for j in range(1, m):
        if cn[j] >= i - 1:
            ndp[j] = dp[j] * (cn[j] - i + 1) % mod
        dp[j] += dp[j-1]
        if dp[j] >= mod:
            dp[j] -= mod
    for j in range(1, m):
        ndp[j] += dp[ba[j]] * b[j]
        ndp[j] %= mod
    dp = ndp
print(sum(dp) % mod)

from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mod = 998244353
a.sort()
dp = [1] + [0] * n
for i in range(1, n + 1):
    x, pt = 1, i - 2
    while pt >= 0 and 2 * a[pt] > a[i - 1]:
        x = x * (n - pt - 2) % mod
        pt -= 1
    dp[i] = (dp[i - 1] * (n - i) + dp[pt + 1] * x) % mod
print(dp[-1])

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mod = 998244353
a.sort()
dp = [1] + [0] * n
for i in range(1, n + 1):
    x, pt = 1, i - 2
    while pt >= 0 and 2 * a[pt] > a[i - 1]:
        x = x * (n - pt - 2) % mod
        pt -= 1
    dp[i] = (dp[i - 1] * (n - i) + dp[pt + 1] * x) % mod
print(dp[-1])

mod = 998244353
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split())) + [0]
    A.sort()

    dp = [[0] * (i+1) for i in range(N+1)]
    dp[0][0] = 1
    l = 0
    for i in range(1, N+1):
        for ll in range(l+1, i):
            if A[ll] * 2 <= A[i]:
                l = ll
            else:
                break
        for j in range(1, l+2):
            dp[i][j] = (dp[l][j-1] + (dp[i][j-1] * (l-j+2))%mod)%mod
        for j in range(i):
            dp[i][j] = (dp[i-1][j] + dp[i][j])%mod
    print(dp[-1][-1])


def __starting_point():
    main()

__starting_point()

M = 998244353 
n = int(input())
l = sorted(map(int, input().split()))[::-1]
out = [0] * n
big = 0
if l[0] >= 2 * l[1]:
    out[1] = 1
    big = 1
for i in range(2, n):
    new = [0] * n
    bigN = 0
    for j in range(i):
        if l[j] >= 2 * l[i]:
            big += out[j]
        else:
            new[j] += out[j] * (i - 1)
            new[j] %= M
    
    new[i] = big
    bigN = (i * big) % M 
        
    out = new
    big = bigN
print((big + sum(out))%M)