Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Emotional Fishermen

time limit per test

4 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard output$$$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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/16/2021 02:16:23 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|