← 返回题目列表

Codeforces · 1437/F

F. 情感渔民

中文机器翻译题面 查看原题

$$$n$$$ 渔民刚刚结束钓鱼假期。第 $$$i$$$ 渔夫捕获了一条重量为 $$$a_i$$$ 的鱼。

渔民们要互相炫耀他们捕获的鱼。为此,他们首先选择展示鱼的顺序(每个渔夫只展示一次他的鱼,因此,形式上,展示鱼的顺序是从 $$$1$$$ 到 $$$n$$$ 的整数排列)。然后他们按照选择的顺序展示他们捕获的鱼。当渔夫展示他的鱼时,他可能会变得高兴,变得悲伤,或者保持满足。

假设渔夫展示了一条重量为 $$$x$$$ 的鱼,之前展示的鱼的最大重量为 $$$y$$$(如果该渔夫是第一个展示他的鱼,则$$$y = 0$$$)。然后:

- 如果$$$x \ge 2y$$$,渔夫变得快乐;
- 如果$$$2x \le y$$$,渔夫会变得悲伤;
- 如果这两个条件都不满足,渔夫就会满意。

如果在所有渔民都按照这个顺序展示他们的鱼之后,每个渔民变得快乐或悲伤,我们就称之为渔民展示他们的鱼情绪化的顺序。计算情感订单数以 $$$998244353$$$ 为模。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5000$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

输出

打印一个整数 — 情感订单的数量,以 $$$998244353$$$ 为模。

示例

输入 #1

4
1 1 4 9

输出 #1

20

输入 #2

4
4 3 2 1

输出 #2

0

输入 #3

3
4 2 1

输出 #3

6

输入#4

8
42 1337 13 37 420 666 616 97

输出#4

19200