Emotional Fishermen
Contest: Educational Codeforces Round 97 (Rated for Div. 2)
Difficulty rating: 2600
Tags: combinatorics, dp, math, two pointers

$$$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 format:
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 format:
Print one integer — the number of emotional orders, taken modulo $$$998244353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Example input:
4
1 1 4 9

Example output:
20

Example input:
4
4 3 2 1

Example output:
0

Editorial:
First of all, sort the fishermen so it is easier to consider them in ascending order.
The key observation that allows us to solve the problem is the following: there will be an increasing sequence of happy fishermen, and all other fishermen will be unhappy.
Consider the fisherman $$$i$$$ which belongs to the increasing sequence. Let's analyze which fisherman will be next to it in the order. It is either a fisherman that will be happy, or a fisherman that will be sad. In the first case, the fish caught by this fisherman must have a size of at least $$$2a_i$$$, in the second case — at most $$$\frac{a_i}{2}$$$.
The first case will be considered later. For the second case, if we know the number of fishermen that were already placed in the order, we know that all of them (except the $$$i$$$-th one) belong to the "sad" category (that is, the fish of every already placed fisherman, except for the $$$i$$$-th one, is at least two times smaller than the fish of the $$$i$$$-th fisherman). So, if we have already placed $$$j$$$ fishermen, the last happy fisherman was the $$$i$$$-th one, and we want to place a sad fisherman, then the number of ways to choose this sad fisherman is exactly $$$cntLess(i) - j + 1$$$, where $$$cntLess(i)$$$ is the number of fishermen $$$k$$$ such that $$$2 a_k \le a_i$$$.
If we can handle the first case, this observation will allow us to solve the problem with dynamic programming. Let $$$dp_{i, j}$$$ be the number of ways to choose $$$j$$$ first fishermen in the order so that the $$$i$$$-th fisherman is the last happy one. The case when the next fisherman is sad can be handled with a transition to the state $$$dp_{i, j + 1}$$$ (don't forget to multiply by the number of ways to choose the next sad fisherman, as described earlier).
What about the case when the next fisherman is happy? We should iterate on the fisherman $$$k$$$ such that $$$a_k \ge 2a_i$$$ and transition from $$$dp_{i, j}$$$ to $$$dp_{k, j + 1}$$$, but this part works in $$$O(n^3)$$$. To get an $$$O(n^2)$$$ solution, we have to speed it up with prefix sums or something like that.